🌶 快速排序（Quick Sort）
简介：
快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
设计思想：
快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。 具体算法描述如下：
从数列中挑出一个元素，称为 “基准”（pivot）；
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
代码实现：
c语言版
void QuickSort(int *arr, int maxlen, int begin, int end) { int i, j; if (begin < end) { i = begin + 1; j = end; while (i < j) { if(arr[i] > arr[begin]) { swap(&arr[i], &arr[j]); j--; } else { i++; } } if (arr[i] >= arr[begin]) { i--; } swap(&arr[begin], &arr[i]); QuickSort(arr, maxlen, begin, i); QuickSort(arr, maxlen, j, end); } } void swap(int *a, int *b) { int temp; temp = *a; *a = *b; *b = temp; }
Java版
/** * 快速排序算法 * @param array * @param low * @param hight * @date 2022/01/20 */ public static void QuickSort(int[] array,int low,int hight){ //if (array.length < 1 || low < 0 || hight >= array.length || low > hight) return null; if(low < hight){ int privotpos = partition(array,low,hight); QuickSort(array,low,privotpos - 1); QuickSort(array,privotpos + 1,hight); } } public static int partition(int[] array,int low,int hight){ int privot = array[low]; while(low < hight){ while(low < hight && array[hight] >= privot) --hight; array[low] = array[hight]; while(low < hight && array[low] <= privot) ++low; array[hight] = array[low]; } array[low] = privot; return low; }
🍑 堆排序（Heap Sort）
简介：
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
设计思想：
将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
代码实现：
c语言版
void Heapify(int *arr, int m, int size) { int i, tmp; tmp = arr[m]; for (i = 2 * m; i <= size; i *= 2) { if (i + 1 <= size && arr[i] < arr[i+1]) { i++; } if (arr[i] < tmp) { break; } arr[m] = arr[i]; m = i; } arr[m] = tmp; } void BulidHeap(int *arr, int size) { int i; for (i = n / 2; i > 0; i--) { Heapify(arr, i, size); } } void swap(int *arr, int i, int j) { int tmp; tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } void HeapSort(int *arr, int size) { int i; BulidHeap(arr, size); for (i = size; i > 1; i--) { swap(arr, 1, i); Heapify(arr, 1, i - 1); } }
Java版
/** * 调整堆 * @param array * @param index * @param length * @date 2022/01/20 */ public static void heapAdjust(int[] array,int index,int length){ //保存当前结点的下标 int max = index; //当前节点左子节点的下标 int lchild = 2*index; //当前节点右子节点的下标 int rchild = 2*index + 1; if(length > lchild && array[max] < array[lchild]){ max = lchild; } if(length > rchild && array[max] < array[rchild]){ max = rchild; } //若此节点比其左右孩子的值小，就将其和最大值交换，并调整堆 if(max != index){ int temp = array[index]; array[index] = array[max]; array[max] = temp; heapAdjust(array,max,length); } } /** * 堆排序 * @param array * @return */ public static int[] heapSort(int[] array){ int len = array.length; //初始化堆，构造一个最大堆 for(int i = (len/2 - 1);i >= 0;i--){ heapAdjust(array,i,len); } //将堆顶的元素和最后一个元素交换，并重新调整堆 for(int i = len - 1;i > 0;i--){ int temp = array[i]; array[i] = array[0]; array[0] = temp; heapAdjust(array,0,i); } return array; }
