今天集中把几种排序的方法列一下，当然最出名的希尔，快排，归并和其优化当然也是满载，说到希尔排序的话，不得不先提到的就是插入排序了，希尔排序就是对直接插入排序的一种优化，下面就是直接插入排序的思想
直接插入排序 1 void InsertSort（int *a, size_t size） 2 { 3 assert（a）; 4 for （int i = 1; i < size; ++i） 5 { 6 int index = i; 7 int tmp = a[index]; 8 int end = index - 1; 9 while （end >= 0 && a[end]>tmp）10 {11 a[end + 1] = a[end];12 end--;13 }14 a[end + 1] = tmp;15 }16 }这就是直接插入排序的代码，思想很简单，代码也很简单为什么希尔排序比直接插入排序更加优化呢？当需要排序的数组过长的时候，有可能出现，插入数据的时候需要把数据插入到数组头的位置，那么数组中需要移动的数据就太多了，效率很低，但是当数组趋于有序的时候，直接插入排序的效率是很高的，所以
希尔排序可以理解为直接插入排序的预排序，让数组更趋于有序，
希尔排序的最后一趟排序就是直接插入排序希尔排序
将一个数组进行分组（就是隔几个元素分为一组）如下图图中选择每隔两个元素分为一组，隔几个元素（设为gap）一组是有讲究的，会影响到排序的效率的，一会就推荐一种算法分组之后，对每一组都进行插入排序，执行完一次所有的分组的插入排序之后算作完成一趟排序，然后减少gap的值，直到最后一次gap的值会变为1，成为直接插入排序下面是代码 1 void ShellSort（int *a,size_t size） 2 { 3 assert（a）; 4 int gap = size; 5 while （gap > 1） 6 { 7 gap = gap / 3 + 1; 8 for （int i = gap; i < size; ++i） 9 {10 int index = i;11 int tmp = a[index];12 int end = index - gap;13 while （end >= 0 && a[end]>a[index]）14 {15 a[end + gap] = a[end];16 end -= gap;17 }18 a[end + gap] = tmp;19 }20 }21 }每次对gap的值进行gap=gap/3+1，为啥？因为比较优，具体应该就是数学问题了，我就不太清楚了。。。。接下来是
选择排序，选择选择，就是每一次选出最大（小）值，然后交换到最高（低）的位置，优化！一次不仅可以选出最小的值，还可以选出最大的，同时选出，同时交换，可以提高效率 1 void SelectSort（int *a,size_t size ） 2 { 3 assert（a）; 4 int min; 5 int max; 6 for （int i = 0; i<size; i++） 7 { 8 min = i; 9 max = size - 1 - i;10 for （int j = i + 1; j<size - i; j++）11 {12 if （a[min]>a[j]）13 {14 min = j;15 }16 if （a[max]<a[j]）17 {18 max = j;19 }20 }21 swap（a[i], a[min]）;22 swap（a[size - 1 - i], a[max]）;23 }24 }思想啥的就不贴了，毕竟是比较简单和基础的排序了
堆排序接下来就是堆排序了！什么是堆，这里我就进行简单的介绍了，
堆的本质是一个数组，将这个数组看成一个二叉树，很抽象，来个图顺序把数组弄成二叉树，大堆（每个父亲节点都比孩子节点的值要大），小堆（每个父亲节点都比孩子节点的值要小，上图就是一个小堆），所谓的堆排序就是把待排序的数组先建堆每一次交换之后将调整的范围缩小一个，这样就能保证，每次交换到最后的数都是大数，并到了自己应该到的位置上去，建堆的过程用到向下调整，，每一次交换之后也要向下调整，堆是一种数据结构，这里就不详解了，之后会整理出堆来，这里介绍堆排序的思想和代码 1 void AdjustDown（int *a, size_t size, int root） 2 { 3 assert（a）; 4 int child = root * 2 + 1; 5 while （child < size） 6 { 7 if （child + 1 < size && a[child + 1] > a[child]） 8 { 9 child++;10 }11 if （a[child]>a[root]）12 {13 swap（a[child], a[root]）;14 root = child;15 child = root * 2 + 1;16 }17 else18 {19 break;20 }21 }22 }23 24 25 void HeapSort（int *a, size_t size）26 {27 assert（a）;28 for （int i = （size - 2） / 2; i >= 0; --i）29 {30 AdjustDown（a, size, i）;31 }32 for （int i = size - 1; i >= 0; --i）33 {34 swap（a[0], a[i]）;35 AdjustDown（a, i, 0）;36 }37 }接下来就是快排了！！这个被誉为十大算法的家伙！！
快速排序快排的思想是拆分递归，直到递归到最深层（就一个元素） 1 int PartionSort（int *a,int left,int right） 2 { 3 int MidIndex = GetMidIndex（a, left, right）; 4 swap（a[MidIndex], a[right]）; 5 int key = a[right]; 6 int begin = left; 7 int end = right - 1; 8 while （begin < end） 9 {10 while （begin < end && a[begin] <= key）11 {12 ++begin;13 }14 while （begin < end && a[end] >= key）15 {16 --end;17 }18 if （begin < end）19 {20 swap（a[begin], a[end]）;//begin<end，比key值小的和比key值大的交换21 }22 }23 if （a[begin] > key）24 {25 swap（a[begin], a[right]）;26 return begin;27 }28 return right;29 }30 31 void QuickSort（int *a,int left,int right）32 {33 assert（a）;34 if （right - left < 1）35 {36 return;37 }38 int boundary = PartionSort（a,left,right）;39 QuickSort（a, left, boundary-1）;40 QuickSort（a, boundary + 1, right）;41 42 }但是不够优化，当每次取的key值恰好比较接近最大值或者最小值的时候，分界递归的时候就会出现分布不均匀，导致效率低下，当划分成两边相等的时候自然比较好，所以加上这个部分会比较好
1 int GetMidIndex（int *a, int left, int right） 2 { 3 assert（a）; 4 int mid = left + （right - left） / 2; 5 if （a[left] < a[right]） 6 { 7 if （a[mid] < a[left]） 8 { 9 return left;10 }11 else if （a[mid] < a[right]）12 {13 return mid;14 }15 else16 return right;17 }18 else19 {20 if （a[mid] < a[right]）21 {22 return right;23 }24 else if （a[mid] < a[left]）25 {26 return mid;27 }28 else29 return left;30 }31 }三数取中法，代码已经更新过了，所以上边的快排已经是用三数取中优化过的
当快排递归到比较深层的时候，被分成小部分的区间内已经趋于有序了，那么采用直接插入排序就可以有效的提高效率！！具体做法就是在QuickSort中的if部分修改，改掉递归结束条件，然后加上直接插入排序的代码就好了
这个不能算是优化，思想有些不同，这次是从同一边走采用cur和prev两个参数，外层的递归还是不变的，只是一次排序不同了 1 int PartionSort2（int *a,int left,int right） 2 { 3 int key = a[right]; 4 int cur = left; 5 int prev = left - 1; 6 while （cur < right） 7 { 8 if （a[cur] < key && prev++ ！= cur） 9 {10 swap（a[prev], a[cur]）;11 }12 cur++;13 }14 swap（a[prev], a[cur]）;15 return prev;16 }
- 忘了把非递归贴上来了，赶紧加上 1 void QuickSort_NonR（int *a） 2 { 3 stack<testnode> s; 4 s.push（testnode（0, 9））; 5 while （！s.empty（）） 6 { 7 testnode top = s.top（）; 8 s.pop（）; 9 int MidIndex = GetMidIndex（a, top._left, top._right）;10 swap（a[MidIndex], a[top._right]）;11 int key = a[top._right];12 int begin = top._left;13 int end =top._right - 1;14 while （begin < end）15 {16 while （begin < end && a[begin] <= key）17 {18 ++begin;19 }20 while （begin < end && a[end] >= key）21 {22 --end;23 }24 if （begin < end）25 {26 swap（a[begin], a[end]）;27 }28 }29 if （a[begin] > key）30 {31 swap（a[begin], a[top._right]）;32 s.push（testnode（top._left, begin））;33 s.push（testnode（begin + 1, top._right））;34 }35 }36 }
最后key值还是会跑到大概中间的位置，和他自己应该在的地方比较接近最后一个排序就是归并排序啦！
归并排序归并排序一上来就将数组分割成两部分，然后不停的分割，直到一个元素不能再分位置，然后开始合并相邻的两个元素，合并之后当然是有序的，有序之后就可以回到上一层，然后不断的进行合并，最后整个数组都有序啦，也就是说要想合并，两个部分都必须是有序的才行。就是类似这样的思想还是不太难理解的实现这样的思想需要开辟辅助空间，因为当两部分有序的数组合并之后还要是有序的才行，需要一个同等大小的数组暂存一下数据 1 void MergeSelection（int *a, int *tmp, int begin1, int end1, int begin2, int end2） 2 { 3 int index = begin1; 4 while （begin1 <= end1 && begin2 <= end2） 5 { 6 if （a[begin1] < a[begin2]） 7 { 8 tmp[index++] = a[begin1++]; 9 }10 else11 tmp[index++] = a[begin2++];12 }13 while （begin1 <= end1）14 {15 tmp[index++] = a[begin1++];16 }17 while （begin2 <= end2）18 {19 tmp[index++] = a[begin2++];20 }21 }22 23 24 void MergeSort（int *a ,int *tmp,int left,int right）25 {26 int mid = left + （right - left） / 2;27 if （left < right）28 {29 30 MergeSort（a, tmp, left, mid）;31 MergeSort（a, tmp, mid + 1, right）;32 MergeSelection（a, tmp, left, mid, mid + 1, right）;33 34 memcpy（a + left, tmp + left, sizeof（int）*（right - left + 1））;35 }36 }tmp是我在测试用例中就开辟好的，直接作为参数传进去
本文永久更新链接地址：http://www.linuxidc.com/Linux/2016-05/131646.htm
易网时代-编程资源站