本次所介绍的排序分别是堆排序、归并排序、快速排序。
void swap(int a[],int i,int j)；//交换下标为i和j的两个元素的值
void printA(int a[],int len)；//打印数组
堆排序：
堆排序是指利用堆这种数据结构所设计的一种排序算法，它是选择排序的一种。在从小到大排序中，需要使用的是大根堆，大根堆的要求是每个节点的值都不大于其父节点的值，根据大根堆的要求可知，最大的值一定在堆顶。这样每次都可以找到待排序元素中最大元素。代码如下：
//调整最大堆 void heapify (int *a,int i,int len) { int left = 2 * i + 1; //左孩子节点下标 int right = 2 * i + 2; //右孩子节点下标 int max = i; //最大元素下标 if (left < len && a[left] > a[max]) //当前最大元素与左孩子比较 { max = left; } if (right < len && a[right] > a[max]) //当前最大元素与右孩子比较 { max = right; } if (max != i) { swap (a,i,max); heapify (a,max,len); //调整被交换的节点 } } //排序 void heapsort (int *a,int len) { int i; for (i = len / 2 - 1;i >= 0;i--) { heapify (a,i,len); //建最大堆 } for (i = len - 1;i > 0;i--) { swap (a,i,0); //交换堆顶与堆尾 heapify (a,0,--len); //调整堆顶，堆大小-1 } } int main() { int a[] = {23,32,46,1,32,56,2,12,48,53,72,20,10,4,23,12,4,5}; int len = sizeof(a) / sizeof(a[0]); heapsort (a,len); printA (a,len); return 0; }
归并排序：
归并排序是建立在归并操作上的一种有效的排序算法。先让每个子序列有序，再将已有序的子序列合并，得到完全有序的序列。需要使用到递归，并且在合并时，需要建一个缓冲区。代码如下：
//归并（合并） void merge (int *a,int left,int right,int mid,int *tmp) { int i = left; int j = mid + 1; int k = 0; while (i <= mid && j <= right) //从小到大依次放入缓冲区 { if (a[i] < a[j]) { tmp[k++] = a[i++]; } else { tmp[k++] = a[j++]; } } //剩下的全部放入缓冲区 while(i <= mid) { tmp[k++] = a[i++]; } while (j <= right) { tmp[k++] = a[j++]; } k = 0; for (i = left;i <= right;i++) //将缓冲区的值传给数组 { a[i] = tmp[k++]; } } //排序 void mergesort (int *a,int left,int right,int *tmp) { if (left >= right) { return; } int mid = (left + right) / 2; mergesort (a,left,mid,tmp); //归并排序左边 mergesort (a,mid + 1,right,tmp); //归并排序右边 merge (a,left,right,mid,tmp); //合并 } int main() { int a[] = {23,32,46,12,56,1,23,20,40,86,32,1,32,4,23,12,4,5}; int len = sizeof(a) / sizeof(a[0]); int tmp[len]; mergesort (a,0,len - 1,tmp); printA (a,len); return 0; }
快速排序：
快速排序的基本思想是选一个基准值，通过一趟排序将要排序的数据分成两部分，比基准值小的和比基准值大的分别放在基准值两边，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。快速排序是对冒泡排序的一种改进。代码如下：
//分区操作，返回基准值下标 int partition (int * a,int left,int right) { int pivot = a[right]; //选右边界为基准值 int index = left; int i; for (i = left;i < right;i++) { if (a[i] < pivot) //比基准值小的一律放基准值左边 { swap (a,i,index); index++; } } swap (a,index,right); //将基准值放到比它大的所有数左边 return index; } //排序 void qSort (int *a,int left,int right) { if (left < right) { int pivot = partition (a,left,right); qSort (a,left,pivot - 1); //将比基准值小的数进行快速排序 qSort (a,pivot + 1,right); //将比基准值大的数进行快速排序 } } int main() { int a[] = {23,32,46,1,32,4,23,12,4,5,23,32,46,12,56,1,23,20,40,86,32,1,32,4,23,12,4,5}; int len = sizeof(a) / sizeof(a[0]); qSort (a,0,len - 1); printA (a,len); return 0; }
有关排序的更多算法和代码实现以及更高效的排序，希望能与大家交流。
