首页 > 代码库 > 【C/C++】排序算法小结
【C/C++】排序算法小结
1、计数排序
如果给定上下界，并且区间不大的话，最适用。
比如对于英文字母数组进行排序。
时间复杂度O(n)，空间复杂度O(n)
void countSort(int A[], int n, int low, int high){ int size = high-low+1; vector<int> count(size, 0); //count[i] represents low+i appears count[i] times in A for(int i = 0; i < n; i ++) { count[A[i]-low] ++; } int ind = 0; for(int i = 0; i < size; i ++) { while(count[i]) { A[ind ++] = low+i; count[i] --; } }}
2、冒泡排序（基础版）
最基础的排序算法，相邻元素两两比较并交换。
时间复杂度O(n2)，空间复杂度O(1)。稳定排序。
void bubbleSort(int A[], int n){ for(int i = 0; i < n; i ++) { for(int j = 0; j < n-i-1; j ++) { if(A[j] > A[j+1]) swap(A[j], A[j+1]); } }}
3、冒泡排序（加速版）
如果中间结果已经有序，即一次遍历过程中不存在需要交换的相邻元素，则结束返回。
时间复杂度O(n2)，空间复杂度O(1)。稳定排序。
void bubbleSortAc(int A[], int n){ bool exchange; for(int i = 0; i < n; i ++) { exchange = false; for(int j = 0; j < n-i-1; j ++) { if(A[j] > A[j+1]) { exchange = true; swap(A[j], A[j+1]); } } if(exchange == false) return; }}
4、选择排序
遍历过程中选择最大元素，与末尾元素交换。
时间复杂度O(n2)，空间复杂度O(1)。不稳定排序。
void selectSort(int A[], int n){ for(int i = n-1; i >= 0; i --) { int max = A[0]; int ind = 0; for(int j = 1; j <= i; j ++) { if(A[j] > max) { max = A[j]; ind = j; } } if(ind != i) swap(A[ind], A[i]); }}
5、插入排序
将当前元素插入局部有序的数组中。
时间复杂度O(n2)，空间复杂度O(1)。稳定排序。
void insertSort(int A[], int n){ for(int i = 1; i < n; i ++) {//insert A[i] into the right place int cur = i-1; int value =http://www.mamicode.com/ A[i]; while(cur >= 0 && A[cur] > value) { A[cur+1] = A[cur]; cur --; } A[cur+1] = value; }}
6、快速排序
最常用的排序，使用pivot将数组分成大小两段，递归完成排序。
时间复杂度平均O(nlogn)，最坏情况（已排序或逆序）O(n2)，空间复杂度O(1)。不稳定排序。
int partition(int A[], int low, int high){ int pivot = A[low]; int vacant = low; while(low < high) { while(high > low && A[high] >= pivot) high --; //A[high] < pivot if(high > low) { A[vacant] = A[high]; vacant = high; } else break; while(low < high && A[low] <= pivot) low ++; //A[low] > pivot if(low < high) { A[vacant] = A[low]; vacant = low; } else break; } A[low] = pivot; return low;}void quickSort(int A[], int low, int high){ if(low < high) { int pos = partition(A, low, high); quickSort(A, low, pos-1); quickSort(A, pos+1, high); }}
7、堆排序
分为建堆与交换两个过程。
通常用于数组中寻找最大/小的k个元素。
时间复杂度O(nlogn)，空间复杂度O(1)。不稳定排序。
void siftDown(int A[], int start, int end){ int temp = A[start]; int i = start; int j = 2*i + 1; //left child while(j <= end) { if(j+1 <= end && A[j]<A[j+1]) j = j+1; //choose the bigger if(temp >= A[j]) break; else { A[i] = A[j]; i = j; j = 2*i + 1; } } A[i] = temp;}void heapSort(int A[], int n){ //build max heap for(int i = (n-2)/2; i >= 0; i --) siftDown(A, i, n-1); //sort for(int i = n-1; i >= 0; i --) { swap(A[0], A[i]); siftDown(A, 0, i-1); //not include the i_th node }}
8、归并排序
分为局部排序与有序归并。
通常用于内存不足，需要与硬盘交互的排序。
时间复杂度O(nlogn)，空间复杂度O(n)。稳定排序。
void merge(int A[], int start, int mid, int end){ int size1 = mid-start+1; int* L = new int[size1]; for(int i = 0; i < size1; i ++) L[i] = A[start+i]; int size2 = end-mid; int* R = new int[size2]; for(int i = 0; i < size2; i ++) R[i] = A[mid+1+i]; int i = 0; int j = 0; int ind = start; while(i < size1 && j < size2) { if(L[i] <= R[j]) { A[ind] = L[i]; ind ++; i ++; } else { A[ind] = R[j]; ind ++; j ++; } } while(i < size1) { A[ind] = L[i]; ind ++; i ++; } while(j < size2) { A[ind] = R[j]; ind ++; j ++; }}void mergeSort(int A[], int start, int end){ if(start < end) { int mid = (start+end)/2; mergeSort(A, start, mid); mergeSort(A, mid+1, end); merge(A, start, mid, end); }}
【C/C++】排序算法小结
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。