最近在准备面试，回顾了一下之前学习的几种排序算法，并参考材料尝试实现。现在此记录一下，以后忘了可以回顾。
直接贴上代码（有许多值得优化的地方）。
package hpp.sort; /** * Created by hpp on 2017/8/4. */ public class SortTest { public static void main(String[] args) { int[] array = {1,2,5,4,7,9,0,8,3,6}; // insertSort(array,array.length); // insertSort2(array,array.length); // shellSort(array); // bubbleSort(array); // quickSort(array, 0, array.length - 1); // selectSort(array); // heapSort(array); mergeSort(array); for(int item:array){ System.out.print(item + " "); } } /** * 直接插入排序，空间复杂度O（1），时间复杂度O（n²） * 适用于基本有序的排序表和数据量不大的排序表 */ public static void insertSort(int[] array, int n){ if(array==null) return; int i,j,temp; for(i=1;i<n;i++){ if(array[i]<array[i-1]){//减少比较移动的次数 temp = array[i]; j = i - 1; while (j>=0){ if (temp<array[j]) { array[j + 1] = array[j]; } else { break; } j--; } array[j+1] = temp; } } } /** * 折半插入排序，空间复杂度O（1），时间复杂度O（n²） * @param array * @param n */ public static void insertSort2(int[] array, int n){ if(array==null) return;; int i,j,temp,low,high,mid; for(i=1;i<n;i++){ temp = array[i]; low = 0; high = i-1; while (low<=high){//找到要插入的位置 mid = (low + high)/2; if(array[mid]>temp){ high = mid - 1; }else { low = mid + 1; } } for(j = i-1;j>=high+1;--j){ array[j+1] = array[j]; } array[high+1] = temp; } } /** * 希尔排序 * @param arr */ private static void shellSort(int[] arr) { int j; int len = arr.length; for(int val=len>>1; val>0; val>>=1) { //下面是对本次的所有分组做直接插入排序 for(int i=val; i<len; i++) { int temp = arr[i]; /* * 为什么每次都用temp比较呢？ * 因为直接插入就是找到temp的合适位置。 * 为什么temp<arr[j-val]这个条件可以放在for内呢？ * 因为原来的组内数据已经有序，找到位置就停止便是。 * 不甚理解的去看直接插入排序吧。 */ for(j=i; j>=val&&temp<arr[j-val]; j-=val) { /* * 为什么是arr[j-val]不是arr[j]呢？ * 因为j=i开始的，而且条件是j>=val&&temp<arr[j-val] */ arr[j] = arr[j-val]; } /* * 注意不是arr[i] = temp * 直接插入排序也是这样的。 * 为什么呢？ * 因为j是位置，i是待插入元素 */ arr[j] = temp; } } } /** * 冒泡排序，空间复杂度O（1），时间复杂度O（n²），稳定 * @param array */ private static void bubbleSort(int[] array){ if (array==null) return; int length = array.length-1; for(int i=0;i<length;i++){ for (int j=length;j>i;j--){ if (array[j-1]>array[j]){ int tmp = array[j]; array[j] = array[j-1]; array[j-1] = tmp; } } } } /** * 快排，空间复杂度最坏O（n）,平均O（logn）,时间复杂度最坏情况下O（n²），平均情况下O（nlogn），不稳定 */ public static void quickSort(int[] array,int left,int right){ if (array==null) return; if (left<right){ int pivot = partition(array,left,right); quickSort(array,left,pivot-1); quickSort(array,pivot+1,right); } } //快排一次划分 private static int partition(int[] array,int left,int right){ int tmp = array[left]; while (left<right){ while (left<right && array[right]>=tmp)// 从右向左找小于tmp的数来填array[left] right--; if (left<right) array[left++] = array[right]; while (left<right && array[left]<tmp)// 从左向右找小于tmp的数来填array[right] left++; if (left<right) array[right--] = array[left]; } array[left] = tmp;//此时的left相当于pivot return left; } /** * 简单选择排序,空间复杂度O(1),时间复杂度O（n²），不稳定 */ public static void selectSort(int[] array){ if (array==null) return; int length = array.length; for(int i=0;i<length;i++){ int min = i;//记录最小元素位置 for(int j=i+1;j<length;j++){ if(array[j]<array[min]){//更新最小元素位置 min = j; } } if (min!=i){//把最小元素和i位置上的元素交换 int tmp = array[i]; array[i] = array[min]; array[min] = tmp; } } } /** * 堆排序：空间复杂度O（1），时间复杂度O（nlogn）,不稳定 */ public static void heapSort(int[] data) { buildMaxHeap(data);// 构建最大堆 for (int i = data.length; i > 1; i--) {// 循环，每次把根节点和最后一个节点调换位置 int tmp = data[0]; data[0] = data[i - 1]; data[i - 1] = tmp; maxHeapify(data, 1, i - 1);// 堆的长度减少1，排除置换到最后位置的根节点 } } // 根据输入数组构建一个最大堆 private static void buildMaxHeap(int[] array) { for (int i = array.length / 2; i > 0; i--) { maxHeapify(array, i, array.length); } } //堆调整，使其生成最大堆 private static void maxHeapify(int[] data, int parentNodeIndex, int heapSize) { // 左子节点索引 int leftChildNodeIndex = parentNodeIndex * 2; // 右子节点索引 int rightChildNodeIndex = parentNodeIndex * 2 + 1; // 最大节点索引 int largestNodeIndex = parentNodeIndex; // 如果左子节点大于父节点，则将左子节点作为最大节点 if (leftChildNodeIndex <= heapSize && data[leftChildNodeIndex - 1]>data[parentNodeIndex - 1]) { largestNodeIndex = leftChildNodeIndex; } // 如果右子节点比最大节点还大，那么最大节点应该是右子节点 if (rightChildNodeIndex <= heapSize && data[rightChildNodeIndex - 1]>data[largestNodeIndex - 1]) { largestNodeIndex = rightChildNodeIndex; } // 最后，如果最大节点和父节点不一致，则交换他们的值 if (largestNodeIndex != parentNodeIndex) { int tmp = data[parentNodeIndex - 1]; data[parentNodeIndex - 1] = data[largestNodeIndex - 1]; data[largestNodeIndex - 1] = tmp; // 交换完父节点和子节点的值，对换了值的子节点检查是否符合最大堆的特性 maxHeapify(data, largestNodeIndex, heapSize); } } /** * 2-路归并排序,空间复杂度O（n）,时间复杂度O(nlogn) */ public static void mergeSort(int[] data) { sort(data, 0, data.length - 1); } public static void sort(int[] data, int left, int right) { if (left >= right) return; // 找出中间索引 int center = (left + right) / 2; // 对左边数组进行递归 sort(data, left, center); // 对右边数组进行递归 sort(data, center + 1, right); // 合并 merge(data, left, center, right); } /** * 将两个数组进行归并，归并前面2个数组已有序，归并后依然有序 * @param data 数组对象 * @param left 左数组的第一个元素的索引 * @param center 左数组的最后一个元素的索引，center+1是右数组第一个元素的索引 * @param right 右数组最后一个元素的索引 */ public static void merge(int[] data, int left, int center, int right) { // 临时数组 int[] tmpArr = new int[data.length]; // 右数组第一个元素索引 int mid = center + 1; // third 记录临时数组的索引 int third = left; // 缓存左数组第一个元素的索引 int tmp = left; while (left <= center && mid <= right) { // 从两个数组中取出最小的放入临时数组 if (data[left] <= data[mid]) { tmpArr[third++] = data[left++]; } else { tmpArr[third++] = data[mid++]; } } // 剩余部分依次放入临时数组（实际上两个while只会执行其中一个） while (mid <= right) { tmpArr[third++] = data[mid++]; } while (left <= center) { tmpArr[third++] = data[left++]; } // 将临时数组中的内容拷贝回原数组中 // （原left-right范围的内容被复制回原数组） while (tmp <= right) { data[tmp] = tmpArr[tmp++]; } } }
