排序合集

排序算法大体可分为两种： 　　　　一种是比较排序，时间复杂度O(nlogn) ~ O(n^2)，主要有：冒泡排序，选择排序，插入排序，归并排序，堆排序，快速排序等。 　　　　另一种是非比较排序，时间复杂度可以达到O(n)，主要有：计数排序，基数排序，桶排序等。 　　　　

排序算法的稳定性：保证排序前后两个相等的数的相对顺序不变。

冒泡排序

它重复地走访过要排序的元素，依次比较相邻两个元素，如果他们的顺序错误就把他们调换过来，直到没有元素再需要交换，排序完成。 方法： 1.比较相邻的元素，如果前一个比后一个大，就把它们两个调换 位置。 2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后 一对。这步做完后，最后的元素会是最大的数。 3.针对所有的元素重复以上的步骤，除了最后一个。 4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

int main() { int A[] = { 4,5,2,7,8,1,9,6 }; // 从小到大冒泡排序 int n = sizeof(A) / sizeof(int); for (int j = 0; j < n - 1; j++) // 每次最大元素就像气泡一样"浮"到数组的最后 { for (int i = 0; i < n - 1 - j; i++) // 依次比较相邻的两个元素,使较大的那个向后移 { if (A[i] > A[i + 1]) // 如果条件改成A[i] >= A[i + 1],则变为不稳定的排序算法 { int temp = A[i]; A[i] = A[j]; A[j] = temp; } } } for (int i = 0; i < n; i++) { printf("%d ", A[i]); } printf("\n"); return 0; }

冒泡排序的改进： 可以让冒泡排序先从前往后比较，再从后向前比较，这是一种优化的方法。

int main() { int A[] = { 6, 5, 3, 1, 8, 7, 2, 4 }; // 从小到大定向冒泡排序 int n = sizeof(A) / sizeof(int); int left = 0; // 初始化边界 int right = n - 1; while (left < right) { for (int i = left; i < right; i++) // 前半轮,将最大元素放到后面 { if (A[i] > A[i + 1]) { int temp = A[i]; A[i] = A[j]; A[j] = temp; } } right--; for (int i = right; i > left; i--) // 后半轮,将最小元素放到前面 { if (A[i - 1] > A[i]) { int temp = A[i]; A[i] = A[j]; A[j] = temp; } } left++; } for (int i = 0; i < n; i++) { printf("%d ", A[i]); } printf("\n"); return 0; }

选择排序

初始时在序列中找到最小（大）元素，放到序列的起始位置作为已排序序列；然后，再从剩余未排序元素中继续寻找最小（大）元素，放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。 代码如下：

void SelectSort(int *array , size_t size) { assert(array); int left = 0; int right = size-1; while (left < right) { int min , max ; min = max= left; for (int i = left; i<=right ; ++i) { if(array[i]<array[min]) { min = i; } if (array[i]>array[max]) { max = i; } swap(array[left],array[min]); if (left = max) { max = min ; } swap(array[right],array[max]); ++left; ++right; } } }

直接插入排序

每次执行，把后面的数插入到前面已经排序好的数组中，直到最后一个完成。 方法： 1.从第一个元素开始，该元素可以认为已经被排序 2.取出下一个元素，在已经排序的元素序列中从后向前扫描 3.如果该元素（已排序）大于新元素，将该元素移到下一位置 4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置 5.将新元素插入到该位置后 6.重复步骤2~5 代码如下：

void InsertSort(int *array,size_t size) { assert(array); for (size_t i=1;i<size;++i) { int tmp=array[i]; int pos=i-1; while (pos >= 0 && array[pos] > tmp) { array[pos+1]=array[pos]; --pos; } array[pos+1]=tmp; } }

插入排序并不适合数据很多的排序。

二分查找排序： 对于插入排序，如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的次数，我们称为二分插入排序。

int main() { int A[] = { 4,3,2,6,5,1,9,8 }; int n = sizeof(A) / sizeof(int); int i, j, get, left, right, middle; for (i = 1; i < n; i++) { get = A[i]; left = 0; right = i - 1; while (left <= right) { middle = (left + right) / 2; if (A[middle] > get) { right = middle - 1; } else { left = middle + 1; } } for (j = i - 1; j >= left; j--) { A[j + 1] = A[j]; } A[left] = get; } for (i = 0; i < n; i++) { printf("%d ", A[i]); } printf("\n"); return 0; }

希尔排序

希尔排序，也叫递减增量排序，是插入排序的一种更高效的改进版本。希尔排序是不稳定的排序算法。 　希尔排序是基于插入排序的以下两点性质而提出改进方法的：

1.插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率； 2.但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。

void ShellSort(int *array,size_t size) { int gap=size; while(gap > 1) { gap=gap/3+1; for (size_t i=gap;i<size;++i) { int tmp=array[i]; int pos=i-gap; while (pos >= 0 && array[pos] > tmp) { array[pos+gap]=array[pos]; pos -= gap; } array[pos+gap]=tmp; } } }

归并排序

归并排序的实现分为递归实现与非递归(迭代)实现。递归实现的归并排序是算法设计中分治策略的典型应用，我们将一个大问题分割成小问题分别解决，然后用所有小问题的答案来解决整个大问题。非递归(迭代)实现的归并排序首先进行是两两归并，然后四四归并，然后是八八归并，一直下去直到归并了整个数组。 归并排序算法主要依赖归并(Merge)操作。归并操作指的是将两个已经排序的序列合并成一个序列的操作，归并操作步骤如下：

1.申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列 2.设定两个指针，最初位置分别为两个已经排序序列的起始位置 3.比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置 4.重复步骤3直到某一指针到达序列尾 5.将另一序列剩下的所有元素直接复制到合并序列尾 代码如下：

void _MergeSort(int *array, int *tmp , int left , int right) { if (left>right) { return ; } int mid = (left/2)+(right/2); if (left < mid) { _MergeSort(array,tmp,left,mid); } if (mid+1 < right) { _MergeSort(array,tmp,mid+1,right); } int index = left; int begin1=left , end1 = mid; int begin2=mid+1, end2 = right; while (begin1 <= end1 && begin2 <= end2) { if (array[begin1]<array[begin2]) { tmp[index++] = array[begin1++]; } else { tmp[index++] = array[begin2++]; } } while (begin1<=end1) { tmp[index++] = array[begin1++]; } while (begin2<=end2) { tmp[index++] = array[begin2++]; } for (int i = left ; i<= right ; ++i) { array[i] = array[i]; } } void MergeSort(int*array , int size) { assert(array); int left=0; int right=size-1; if ((right-left)>=15) { int *tmp= new int[size]; _MergeSort(array,tmp,0,size-1); delete[] tmp; } else { InsertSort(array,(right-left));// } }

堆排序

堆排序是指利用堆这种数据结构所设计的一种选择排序算法。堆是一种近似完全二叉树的结构（通常堆是通过一维数组来实现的），并满足性质：以最大堆（也叫大根堆、大顶堆）为例，其中父结点的值总是大于它的孩子节点。

代码如下：

Heap(T* arr, const int size) { assert(arr); for(size_t i = 0; i < size; i++) _arr[i] = arr[i]; //建堆 for(int i = (size-2)/2; i >= 0; i-- ) { _AdJustDown(i, size); } } void _AdJustDown(int parent, int size) { int child = parent*2 + 1; while(child < size) { if(child + 1 < size && Campare()(_arr[child+1],_arr[child])) ++child; if(Campare()(_arr[child],_arr[parent])) { swap(_arr[child],_arr[parent]); parent = child; child = parent*2 + 1; } else break; } } void _AdJustUp(int size) { int child = size - 1; while(child) { int parent = (child - 1)/2; if(Campare()(_arr[child],_arr[parent])) { swap(_arr[child],_arr[parent]); child = parent; } else break; } }

快速排序

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序n个元素要O(nlogn)次比较。在最坏状况下则需要O(n^2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他O(nlogn)算法更快，因为它的内部循环可以在大部分的架构上很有效率地被实现出来。

　　快速排序使用分治策略来把一个序列分为两个子序列。步骤为： 1.从序列中挑出一个元素，作为”基准”. 2.把所有比基准值小的元素放在基准前面，所有比基准值大的元素放在基准的后面（相同的数可以到任一边），这个称为分区操作。 3.对每个分区递归地进行步骤1~2，递归的结束条件是序列的大小是0或1，这时整体已经被排好序了。

void quickSort(int *array, int left, int right) { if (left< right) { int i = left, j = right, x = array[left]; while (i < j) { while(i < j && array[j]>= x) j--; if(i < j) array[i++] = array[j]; while(i < j && array[i]< x) i++; if(i < j) array[j--] = array[i]; } array[i] = x; quickSort(array, left, i - 1); quickSort(array, i + 1, right); } }

对于快排还有很多优化的地方，在下次博客中将会讨论。