经典排序方法及细节小结(2)
紧接上篇的插入排序 交换排序算法的分析小结，这一篇小结经典排序算法中另外几个算法
选择排序
假使对一个n个大小的序列排序
（1）直接选择排序
思路：
①遍历一遍数组，选择一个最大(小)的值将其放到最后的位置
②在剩下的N-1个元素中，再选一个最大(小)的放到后面（倒数第二位置）
③不断重复以上操作，当只剩下一个元素时结束算法
优化：
操作①时 可以找到最大值和最小值，将最大值放到最后的同时还可以把最小值放到最前面，这样的话一趟排序就能确定两个元素的位置了，一定程度上提高了效率。
优化中注意：如果最大元素本来就是数组首元素即a[left]，当最小数和a[left]交换位置后最大元素的位置已经改变了，这就会导致排序错误。
注意了以上问题就容易写出代码：
void SelectSort(int* arr, size_t length) { assert(arr && length > 0); int left = 0; int right = length - 1; while(left < right) { int min = left; int max = left; for(int i = left; i <= right; ++i) { if(arr[i] < arr[min]) min = i; if(arr[i] > arr[max]) max = i; } Swap(&arr[left], &arr[min]); if(left == max) //max 对应a[left] max = min; Swap(&arr[right], &arr[max]); left++; right--; // Print(arr, length); } }
时间复杂度：最好：O(N*N) 最坏：O(N*N) 平均：O(N*N)
空间复杂度：O(1)
稳定性：不稳定
（2）堆排序
堆排序以其不错排序效率，以及O(1)的空间复杂度成为实际应用中最为广泛的一种排序。
实现排序之前，先介绍一个建堆和实现堆排都会用到的调整算法：向下调整算法
它的作用就是将要调整元素向下调整至一个合适的位置，使该元素子树结点都比它小，父辈结点都比它大。
typedef int DataType; void AdjustDownToBigHeap(DataType* arr, size_t n, size_t curRoot) { assert(arr); size_t parent = curRoot; size_t child = (parent<<1) + 1; while(child < n) { if(arr[child] < arr[child+ 1] && child+1 < n) //找到更大的子结点 ++child; if(arr[child] > arr[parent]) //子结点比父结点大，就交换 Swap(&arr[child], &arr[parent]); //继续往下调整 parent = child; child = (parent<<1)+ 1; } }
堆排实现思路：
①首先将数组按排序码大小建堆，若排升序，建大堆(建大堆很关键)；（这里假设排升序；若是排降序，就建小堆）
②begin指向堆顶，end指向堆尾，堆顶堆尾元素相交换 (此时堆顶就是排序码最大的元素了)，堆尾元素前移(–end)，堆的范围少1。
③再将堆顶元素向下调整，在新范围内让堆继续保持大堆的样式
④重复②③，直到end = 0 结束(n−2)>>1
如对序列{10,20,3,12,16,18,25 ,17,14,19} 建好大堆以后，交换堆头堆尾的值，然后向下调整过程如下：
注意：
排升序是不能建小堆的，因为小堆一次只能确定出来最小的那个元素值，虽然小堆中每一个节点的子树的结点都比根结点的值小，但是无法确定左右子结点的谁更小一点，这样排序过程中就无法确定次最小的元素，要排序的话就得重新建堆了，十分拉低效率的。
堆排代码：
void HeapSort(DataType* arr, int n) { assert(arr); //建一个大堆 int i = (n -1)>>1; for(; i >= 0; --i) { AdjustDownToBigHeap(arr, n, i); //向下调整算法 } //堆头堆尾交换位置，将堆头位置处的值向下调整 int end = n - 1; while(end > 0) { Swap(&arr[0], &arr[end]); AdjustDownToBigHeap(arr, end, 0); --end; } }
时间复杂度：最好：O(NlogN) 最坏：O(NlogN) 平均：O(NlogN)
空间复杂度：O(1)
稳定性：不稳定
归并排序
归并排序和快排思路基本相同，只不过归并排序额外开辟了O(N)的空间来帮助排序，使得在它最坏的情况也能保持O(NlogN)的时间复杂度，所以相对来说，它是一种更加优良的排序算法，只是耗费了更多的空间。
思路：
①当二分为只剩下两个或一个元素的时候，比较大小排序。
②递归回溯时，借助开辟的空间将数组两两进行合并，并且合并后保持有序。
③回溯完毕后，整个数组就有序了 。
注意：
在利用开辟的空间进行合并的时候，采取的方法两条链表合并是一样的，只是它不能像链表那样直接进行结点连接；这里是是按排序码大小依次将放进开辟的数组里面，这样数组里面存放的序列就是有序的了，然后再将这段序列拷贝回原来位置。
代码：
void MergeArr(int* arr, int left, int mid, int right) { int* tmp = (int*)malloc(sizeof(int) * (right -left +1)); //开辟一个中间数组 int begin1 = left, end1 = mid; int begin2 = mid + 1, end2 = right; int index = 0; //归并在一起 while(begin1 <= end1 && begin2 <= end2) { if(arr[begin1] <= arr[begin2]) tmp[index++] = arr[begin1++]; else tmp[index++] = arr[begin2++]; } //如果分成两个数组中一边还有剩余,烤过去 while(begin1 <= end1) tmp[index++] = arr[begin1++]; while(begin2 <= end2) tmp[index++] = arr[begin2++]; //将tmp保存好的有序数据再拷回原数组 for(int i = left; i<= right; ++i) arr[i] = tmp[i-left]; free(tmp); } void MergeSort(int* arr, int left, int right) { assert(arr); if(left >= right) return; int mid = left + ((right - left)>> 1); MergeSort(arr, left, mid); MergeSort(arr, mid+ 1, right); MergeArr(arr, left, mid, right); }
时间复杂度：最好：O(NlogN) 最坏：O(NlogN) 平均：O(NlogN)
空间复杂度：O(N)
对应两个相同排序码的元素，在排序合并时，在前面的就会先进行合并，合并后并不会影响它们的相对位置
稳定性：稳定
计数排序
基本思路就是对于给定的输入序列中的每一个元素x，统计该序列中值为x的元素的个数 。一旦有了这个信息，就可以将x直接存放到最终的输出序列的正确位置上。它的原理跟哈希表的K-V模型类似。
思路：
①遍历一遍数组，得出数组的范围range，创建一个大小为range的数组，即哈希表，初始化为全0。
②再从头开始遍历数组，数字重复出现一次，在其相应的位置对应的数值加1。
③从左到右开始遍历哈希表，将数值不为0的位置的下标存储到原数组中，且数值是多少就存储多少个 。
注意：
①此种排序是依靠一个辅助数组来实现，不基于比较，遍历常数遍数组即可，所以时间复杂度较低；但由于要一个辅助数组C，所以空间复杂度要大一些，由于计算机的内存有限，所以这种算法适合排范围小、值密集的序列，不适合范围很大的序列。
②开辟哈希表的大小时考虑这样一个问题 例如我有10000个数，10001~20000，这种情况我们就需要遍历一遍数据，找出最大值与最小值，求出数据范围，这样我们就开辟10000个空间，用1代表10001,10000代表20000。；而不是直接就开辟20000个数存储空间浪费大量的空间。
时间复杂度：不难看出我们总需要两遍遍历，第一遍统计字数据出现次数，遍历原数据，复杂度为O(N)，第二遍遍历哈希表，向原空间写数据,又遍历了范围次（range），所以总的时间复杂度为O(N+range)。
空间复杂度：开辟了范围（range）大小的辅助哈希表，所以空间复杂度为O(range)。
稳定性：可稳定
代码：
void CountSort(int* arr, int length) { assert(arr && length > 0); int max = arr[0]; int min = arr[0]; //选出最大数与最小数，确定哈希表的大小 for (int i = 0; i < length; ++i) { if (arr[i] > max) max = arr[i]; if (arr[i] < min) min = arr[i]; } int range = max - min + 1; int *pCount = (int*)malloc(sizeof(int) * range); memset(pCount, 0, sizeof(int)*range); //将开辟空间初始化成0 //确定相同元素的个数 for (int i = 0; i < length; ++i) pCount[arr[i] - min]++; //将数据重新写回数组 int j = 0; for (int i = 0; i < range; ++i) { while (pCount[i]-- > 0) //大小为i+ min的元素有pCount[i]个 arr[j++] = i + min; } free(pCount); }