排序排序 - 锐客网

本文记录几个基础的排序算法。排序算法分为插入排序、交换排序、选择排序等几大类。
插入排序 1. 直接插入排序 O(n2) 【排序】直接插入排序思路：将数组分为有序区和无序区，每次插入都在无序区中取一个元素，插入到有序区合适的位置。排序开始时，默认第一个元素有序，随后取第2 3 ... 个元素与有序区的元素进行对比，插入。

原始数组： 5, 2, 6, 7, 1, 3, 排序过程：当前是第2个元素2插入：2, 5, 6, 7, 1, 3, 当前是第3个元素6插入：2, 5, 6, 7, 1, 3, 当前是第4个元素7插入：2, 5, 6, 7, 1, 3, 当前是第5个元素1插入：1, 2, 5, 6, 7, 3, 当前是第6个元素3插入：1, 2, 3, 5, 6, 7, 排序数组 1, 2, 3, 5, 6, 7,

算法如下：

public static void insertSort(int[] numbers){ int insert; for (int i = 1; i < numbers.length; i++){ //System.out.print("当前是第" + (i+1) + "个元素" + numbers[i] +"插入："); insert = numbers[i]; int j = i-1; //有序部分的个数 while(j>= 0 && numbers[j] > insert){//有序部分从右到左比较，若大于插入元素，则后移 numbers[j+1] = numbers[j]; //元素后移 j--; } numbers[j+1] = insert; //在需要的位置插入 //fore(numbers); } }

2. 折半插入排序折半插入排序的思路和直接插入排序类似：将数组分为有序区和无序区，每次插入都在无序区中取一个元素，然后通过折半查找的方式，找出插入的位置是在左半区还是在右半区，找到插入的半区后，插入到有序区合适的位置。排序开始时，默认第一个元素有序，随后取第2 3 ... 个元素与有序区的元素进行对比，插入。

public static void insertSort2(int[] numbers) { int low, high, mid; int insert; for (int i = 1; i < numbers.length; i++) { //System.out.print("当前是第" + (i+1) + "个元素" + numbers[i] +"插入："); insert = numbers[i]; low = 0; high = i - 1; while (low <= high) {//在有序区中，折半查找插入的位置 mid = (low + high) / 2; if (insert < numbers[mid]) {//插入点在左半区，设置high为中点的左边 high = mid - 1; } else//插入点在右半区，设置high为中点的右边 low = mid + 1; } for (int j = i-1; j>=high+1; j--){ numbers[j + 1] = numbers[j]; //元素后移 } numbers[high + 1] = insert; //在需要的位置插入 //fore(numbers); } }

3. 希尔排序 O(n1.3) 希尔排序实际上是一种分组插入的方法，思想：选定一个小于n的整数d1，作为一个增量，将距离间隔为d的元素分组，然后在组内进行直接插入排序；然后取第二个增量d2 关于d的选取，这里建议d1 = n / 2, di+1=di / 2。

原始数组： 5, 2, 6, 7, 1, 3, 排序过程：增量gap=3 结果：5, 1, 3, 7, 2, 6, 增量gap=1 结果：1, 2, 3, 5, 6, 7, 排序数组 1, 2, 3, 5, 6, 7,

算法：

public static void shellSort(int[] numbers) { int gap; gap = numbers.length / 2; //增量初始值 while (gap > 0) { for (int i = gap; i < numbers.length; i++) { //相隔gap的元素组进行直接插入排序 int temp = numbers[i]; int j = i - gap; while (j >= 0 && temp < numbers[j]) { //组内移动 numbers[j + gap] = numbers[j]; j = j - gap; } numbers[j + gap] = temp; } //System.out.print("增量gap=" + gap + " 结果："); //fore(numbers); gap = gap / 2; } }

交换排序 1. 冒泡排序 O(n2) 冒泡排序，也称气泡排序，对每两两相邻的关键字进行比较，使得关键字较大的排到数组的后边。一次排序后，得到的结果就将目前最大的元素放置到数组的后部，不断重复该过程，直到所有元素有序。（也有部分冒泡排序每次将最小的部分排列到数组最前端，这两者思想都是一致的）

原始数组： 5, 2, 6, 7, 1, 3, 第1趟排序： 2, 5, 6, 7, 1, 3, 2, 5, 6, 1, 7, 3, 2, 5, 6, 1, 3, 7, 第2趟排序： 2, 5, 1, 6, 3, 7, 2, 5, 1, 3, 6, 7, 第3趟排序： 2, 1, 5, 3, 6, 7, 2, 1, 3, 5, 6, 7, 第4趟排序： 1, 2, 3, 5, 6, 7, 第5趟排序：第6趟排序：排序数组 1, 2, 3, 5, 6, 7,

public static void bubbleSort(int[] a){ int temp; for(int i=0; ia[j+1]){ temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; //fore(a); //输出 } } } }

可以发现，在第5趟排序中，根本就没有交换元素，那么就表明所有元素已经按顺序排列，那么就没比较进行第六趟的比较，因此做如下优化：通过一个boolean判断是否发生交换，如果没有发生交换，则结束算法。

public static void bubbleSort2(int[] a){ int temp; boolean exchange; //是否做交换 for(int i=0; ia[j+1]){ temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; exchange = true; fore(a); } } if (!exchange){//本趟没有发生交换，中途结束算法 return; } } }

2. 快速排序 O(nlog2n) 快速排序的思想：

选择一个基准base，把小于base的数值移到base左边，把大于base的数值移到右边。（此时数组中会分为小于base的左部，和大于base的右部）
递归将小于base和大于base的两部分重复第一步，直到递归完成。
代码实现：

public static void quickSort2(int[] numbers, int start, int end) { int base = numbers[start]; int i = start, j = end; int temp; //临时存储，用作交换 do { while (numbers[i] < base && i < end) {//i从左到右找到第一个大于等于基准的值 i++; } while (numbers[j] > base && j > start) { //j从右到左找到第一个小于等于基准的值 j--; } if (i <= j) {//左右两侧都找到后，交换其位置，并将i后移，j左移 temp = numbers[i]; numbers[i] = numbers[j]; numbers[j] = temp; i++; j--; } } while (i <= j); if (start < j) { quickSort2(numbers, start, j); //递归小于base的左部 } if (end > i) { quickSort2(numbers, i, end); //递归大于base的右部 } }

算法分析：
由于快速排序的思想分为左右两部分递归，可以快速记忆时间复杂度为O(nlog2n)
选择排序 1. 直接选择排序 O(n2) 直接选择排序思想：在当前无序区中选择最小的关键字与无序区的第一个元素进行交换，直到n-1次排序后，整个数组递增有序。

原始数组： 5, 2, 6, 7, 1, 3, 排序过程：第1次排序：1, 2, 6, 7, 5, 3, 第2次排序：1, 2, 6, 7, 5, 3, 第3次排序：1, 2, 3, 7, 5, 6, 第4次排序：1, 2, 3, 5, 7, 6, 第5次排序：1, 2, 3, 5, 6, 7, 排序数组 1, 2, 3, 5, 6, 7,

算法：

public static void selectSort(int[] numbers) { for (int i = 0; i < numbers.length - 1; i++) {//第i次排序 int k = i; //标记最小值的位置 for (int j = i + 1; j < numbers.length; j++) {//在无序区中选择最小的key if (numbers[j] < numbers[k]) { k = j; } } if (k != i) {//交换 int temp = numbers[i]; numbers[i] = numbers[k]; numbers[k] = temp; } System.out.print("第" + (i + 1) + "次排序："); fore(numbers); } }

2. 堆排序堆排序是一种树形选择排序方法，在排序时将数组看成是一颗完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子节点之间的内在联系，在当前无序区中选择关键字最大的元素。
堆（完全二叉树）的定义n个关键字的序列K1, K2... Kn，当且仅当该序列满足以下属性：

Ki <= K2i且 Ki <= K2i+1 ：小根堆
或者：
Ki >= K2i且 Ki >= K2i+1 ：大根堆

算法思想：堆排序的关键在于构造初始堆，假设完全二叉树的某一个节点i，它的左右子树都是堆，这时就需要将R[i]和R[2i]、R[2i + 1]之间的最大者进行比较，如果R[i]较小，那么就将其与较大的孩子进行交换，这个交换过程中，可能会导致下一级的堆被破坏，因此需要用上述的方法递归构造下一级堆。
调整堆算法：

/** * 调整堆算法 * * @param numbers 数组 * @param low要调整的节点 * @param high最后一个节点的位置 */ public static void sift(int[] numbers, int low, int high) { int i = low, j = 2 * i; //j是i的左节点 int temp = numbers[i]; while (j <= high) { if (j < high && numbers[j] < numbers[j + 1]) {//如果右孩子较大，则将j指向右孩子 j++; } if (temp < numbers[j]) { numbers[i] = numbers[j]; //将numbers[j]调整到双亲节点上 i = j; j = 2 * i; //修改i、j的值 } else break; } numbers[i] = temp; //被筛选的节点（要调整的节点）放置到最终位置 }

在初始堆构造好后，根节点是最大的关键字节点，将其放置到序列的最后（和最后一个叶子节点交换），由于最大元素已经归为，待排序的元素会减少一个，根节点也改变了，就需要重新调用sift算法调整堆；然后重复上述步骤，直到完全二叉树只剩最后一个根为止。

原始数组： 5, 2, 6, 7, 1, 3, 排序过程：调整堆：5, 2, 6, 7, 1, 3, 调整堆：5, 7, 6, 2, 1, 3, 调整堆：7, 6, 5, 2, 1, 3, 初始堆完成：7, 6, 5, 2, 1, 3, 调整堆：6, 5, 3, 2, 1, 7, 调整堆：5, 3, 1, 2, 6, 7, 调整堆：3, 2, 1, 5, 6, 7, 调整堆：2, 1, 3, 5, 6, 7, 调整堆：1, 2, 3, 5, 6, 7, 排序数组 1, 2, 3, 5, 6, 7,

/** * 堆排序 * * @param numbers 数组 */ public static void HeapSort(int[] numbers) { int temp; int n = numbers.length-1; for (int i = n / 2; i >= 0; i--) {//构造初始堆 sift(numbers, i, n); } System.out.print("初始堆完成："); fore(numbers); for (int i = n; i >= 1; i--) { temp = numbers[0]; //将最后一个元素和当前区内的第一个节点交换 numbers[0] = numbers[i]; numbers[i] = temp; sift(numbers, 0, i - 1); //得到i-1个节点的堆 } }