江苏龙网

  1. 主页 > 生活百科 > >

十大排序算法，你会几种？( 三 )

排序算法


快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists） 。
（1）算法步骤

步骤1：从数列中挑出一个元素，称为 "基准"（pivot）；步骤2：重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边） 。在这个分区退出之后，该基准就处于数列的中间位置 。这个称为分区（partition）操作；步骤3：递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；
（2）过程演示
十大排序算法，你会几种？

文章插图
 
（3）代码实现
public class QuickSort implements IArraySort {@Overridepublic int[] sort(int[] sourceArray) throws Exception {// 对 arr 进行拷贝，不改变参数内容int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);return quickSort(arr, 0, arr.length - 1);}private int[] quickSort(int[] arr, int left, int right) {if (left < right) {int partitionIndex = partition(arr, left, right);quickSort(arr, left, partitionIndex - 1);quickSort(arr, partitionIndex + 1, right);}return arr;}private int partition(int[] arr, int left, int right) {// 设定基准值（pivot）int pivot = left;int index = pivot + 1;for (int i = index; i <= right; i++) {if (arr[i] < arr[pivot]) {swap(arr, i, index);index++;}}swap(arr, pivot, index - 1);return index - 1;}private void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}堆排序（Heap Sort）堆排序是指利用堆这种数据结构所设计的一种排序算法 。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点 。堆排序可以说是一种利用堆的概念来排序的选择排序 。分为两种方法：
  • 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
  • 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；
堆排序的平均时间复杂度为 O(n log n) 。
（1）算法步骤
步骤1：将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；步骤2：将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；步骤3：由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn) 。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成；
（2）过程演示
十大排序算法，你会几种？

文章插图
 
（3）代码实现
public class HeapSort implements IArraySort {@Overridepublic int[] sort(int[] sourceArray) throws Exception {// 对 arr 进行拷贝，不改变参数内容int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);int len = arr.length;buildMaxHeap(arr, len);for (int i = len - 1; i > 0; i--) {swap(arr, 0, i);len--;heapify(arr, 0, len);}return arr;}private void buildMaxHeap(int[] arr, int len) {for (int i = (int) Math.floor(len / 2); i >= 0; i--) {heapify(arr, i, len);}}private void heapify(int[] arr, int i, int len) {int left = 2 * i + 1;int right = 2 * i + 2;int largest = i;if (left < len && arr[left] > arr[largest]) {largest = left;}if (right < len && arr[right] > arr[largest]) {largest = right;}if (largest != i) {swap(arr, i, largest);heapify(arr, largest, len);}}private void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}计数排序（Counting Sort）计数排序 的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中 。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数 。
计数排序是一种稳定的排序算法 。计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数 。然后根据数组C来将A中的元素排到正确的位置 。它只能对整数进行排序 。（1）算法步骤
步骤1：找出待排序的数组中最大和最小的元素；步骤2：统计数组中每个值为i的元素出现的次数，存入数组C的第i项；步骤3：对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；步骤4：反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1；


推荐阅读


上一篇：在头条上怎么赚钱？告诉你五种方法，绝对干货

下一篇：吸引人的文案句子有哪些？