电子设备知识网-中国电子设备,国内最专业电子设备平台
电子设备知识网-中国电子设备,国内最专业电子设备平台

C++中十大排序算法前五个详解

本期是C++++基础语法分享的第十五节,今天给大家来梳理一下十大排序算法前五个!

冒泡排序

冒泡排序思路:

1. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。

2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。

3. 针对所有的元素重复以上的步骤,除了最后一个。

4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

示例:

void BubbleSort(vector《int》& v) { int len = v.size(); for (int i = 0; i 《 len – 1; ++i) for (int j = 0; j 《 len – 1 – i; ++j) if (v[j] 》 v[j + 1]) swap(v[j], v[j + 1]);}

// 模板实现冒泡排序template《typename T》 //整數或浮點數皆可使用,若要使用物件(class)時必須設定大於(》)的運算子功能void bubble_sort(T arr[], int len) { for (int i = 0; i 《 len – 1; i++) for (int j = 0; j 《 len – 1 – i; j++) if (arr[j] 》 arr[j + 1]) swap(arr[j], arr[j + 1]);}

// 冒泡排序(改进版)void BubbleSort_orderly(vector《int》& v) { int len = v.size(); bool orderly = false; for (int i = 0; i 《 len – 1 && !orderly; ++i) { orderly = true; for (int j = 0; j 《 len – 1 – i; ++j) { if (v[j] 》 v[j + 1]) { // 从小到大 orderly = false; // 发生交换则仍非有序 swap(v[j], v[j + 1]);

} } }}

选择排序

选择排序思路:

1. 在未排序序列中找到最小(大)元素,存放到排序序列的起始位置

2. 从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾

3. 以此类推,直到所有元素均排序完毕

示例:

void SelectionSort(vector《int》& v) { int min, len = v.size(); for (int i = 0; i 《 len – 1; ++i) { min = i; for (int j = i + 1; j 《 len; ++j) { if (v[j] 《 v[min]) { // 标记最小的 min = j; } } if (i != min) // 交换到前面 swap(v[i], v[min]); }}

// 模板实现template《typename T》 void Selection_Sort(std::vector《T》& arr) { int len = arr.size();

for (int i = 0; i 《 len – 1; i++) { int min = i; for (int j = i + 1; j 《 len; j++) if (arr[j] 《 arr[min]) min = j; if(i != min) std::swap(arr[i], arr[min]); }}

插入排序

插入排序思路:

1. 从第一个元素开始,该元素可以认为已经被排序

2. 取出下一个元素,在已经排序的元素序列中从后向前扫描

3. 如果该元素(已排序)大于新元素,将该元素移到下一位置

4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置

5. 将新元素插入到该位置后

6. 重复步骤2~5

示例:

void InsertSort(vector《int》& v){ int len = v.size(); for (int i = 1; i 《 len; ++i) { int temp = v[i]; for(int j = i – 1;

j 》= 0; –j) { if(v[j] 》 temp) { v[j + 1] = v[j]; v[j] = temp; } else break; } }}

快速排序

快速排序思路:

1. 选取第一个数为基准

2. 将比基准小的数交换到前面,比基准大的数交换到后面

3. 对左右区间重复第二步,直到各区间只有一个数

void QuickSort(vector《int》& v, int low, int high) { if (low 》= high) // 结束标志 return; int first = low; // 低位下标 int last = high; // 高位下标 int key = v[first]; // 设第一个为基准

while (first 《 last) { // 将比第一个小的移到前面 while (first 《 last && v[last] 》= key) last–; if (first 《 last) v[first++] = v[last];

// 将比第一个大的移到后面 while (first 《 last && v[first] 《= key) first++; if (first 《 last) v[last–] = v[first]; } // 基准置位 v[first] = key; // 前半递归 QuickSort(v, low, first – 1); // 后半递归 QuickSort(v, first + 1, high);

}

// —————————————————-

// 模板实现快速排序(递归)template 《typename T》void quick_sort_recursive(T arr[], int start, int end) { if (start 》= end) return; T mid = arr[end];

int left = start, right = end – 1; while (left 《 right) { while (arr[left] 《 mid && left 《 right) left++; while (arr[right] 》= mid && left 《 right) right–; std::swap(arr[left], arr[right]); } if (arr[left] 》= arr[end]) std::swap(arr[left], arr[end]); else left++; quick_sort_recursive(arr, start, left – 1);

quick_sort_recursive(arr, left + 1, end);}template 《typename T》 //整數或浮點數皆可使用,若要使用物件(class)時必須設定“小於”(《)、“大於”(》)、“不小於”(》=)的運算子功能void quick_sort(T arr[], int len) { quick_sort_recursive(arr, 0, len – 1);}

// —————————————————-

// 模板实现快速排序(迭代)struct Range { int start, end; Range(int s = 0, int e = 0) { start = s, end = e;

}};template 《typename T》 // 整數或浮點數皆可使用,若要使用物件(class)時必須設定“小於”(《)、“大於”(》)、“不小於”(》=)的運算子功能void quick_sort(T arr[], const int len) { if (len 《= 0) return; // 避免len等於負值時宣告堆疊陣列當機 // r[]模擬堆疊,p為數量,r[p++]為push,r[–p]為pop且取得元素 Range r[len];

int p = 0; r[p++] = Range(0, len – 1); while (p) { Range range = r[–p]; if (range.start 》= range.end) continue; T mid = arr[range.end]; int left = range.start, right = range.end – 1;

while (left 《 right) { while (arr[left] 《 mid && left 《 right) left++; while (arr[right] 》= mid && left 《 right) right–; std::swap(arr[left], arr[right]);

} if (arr[left] 》= arr[range.end]) std::swap(arr[left], arr[range.end]); else left++; r[p++] = Range(range.start, left – 1); r[p++] = Range(left + 1, range.end); }}

堆排序

堆排序:(最大堆,有序区)。从堆顶把根卸出来放在有序区之前,再恢复堆。

#include 《iostream》#include 《algorithm》using namespace std;

// 堆排序:(最大堆,有序区)。从堆顶把根卸出来放在有序区之前,再恢复堆。

void max_heapify(int arr[], int start, int end) { //建立父節點指標和子節點指標 int dad = start; int son = dad * 2 + 1; while (son 《= end) {

//若子節點指標在範圍內才做比較 if (son + 1 《= end && arr[son] 《 arr[son + 1])

//先比較兩個子節點大小,選擇最大的 son++; if (arr[dad] 》 arr[son]) //如果父節點大於子節點代表調整完畢,直接跳出函數 return; else { //否則交換父子內容再繼續子節點和孫節點比較 swap(arr[dad], arr[son]); dad = son; son = dad * 2 + 1; } }}

void heap_sort(int arr[], int len) { //初始化,i從最後一個父節點開始調整 for (int i = len / 2 – 1; i 》= 0; i–) max_heapify(arr, i, len – 1);

//先將第一個元素和已经排好的元素前一位做交換,再從新調整(刚调整的元素之前的元素),直到排序完畢 for (int i = len – 1; i 》 0; i–) { swap(arr[0], arr[i]); max_heapify(arr, 0, i – 1); }}

int main() { int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };

int len = (int) sizeof(arr) / sizeof(*arr); heap_sort(arr, len); for (int i = 0; i 《 len; i++) cout 《《 arr[i] 《《 ‘ ’; cout 《《 endl; return 0;}

今天的分享就到这里了,大家要好好学C++哟~

责任编辑:haq

未经允许不得转载:电子设备知识网 » C++中十大排序算法前五个详解

分享到: 生成海报