排序算法

排序算法

资料冒泡排序 实现简单选择排序 实现堆排序 特性实现直接插入排序 特性实现二分插入排序 实现希尔排序 特性实现快速排序 实现归并排序 特性实现计数排序 特性实现桶排序 特性实现基数排序 特性实现

资料

面试中的 10 大排序算法总结

冒泡排序

从后往前循环比较相邻两数，小数前大数后，一遍完成最小数即排在最前，最后循环排序

实现

public static void bubbleSort(int[] arr) { if (arr == null || arr.length == 0) return; int index = arr.length - 1; for (int i = 0; i < index; i++) { for (int j = index; j > i; j--) { // 最小在最前 if (arr[j] < arr[j - 1]) { // 小在前大在后 exchange(arr, j, j - 1); } } } } private static void exchange(int[] arr, int i, int j) { arr[i] = arr[i] ^ arr[j]; arr[j] = arr[i] ^ arr[j]; arr[i] = arr[i] ^ arr[j]; }

简单选择排序

从前向后循环排序，查找最小数互换位置

实现

public static void selectSort(int[] arr) { if (arr == null || arr.length == 0) return; int minIndex; int length = arr.length; for (int i = 0; i < length - 1; i++) { // 选择最小 minIndex = i; for (int j = i + 1; j < length; j++) { if (arr[j] < arr[minIndex]) { minIndex = j; } } // 置最前 if (minIndex != i) { exchange(arr, i, minIndex); } } }

堆排序

使用二叉堆的特性，调整为大顶堆，选择最大值出堆，最后循环调整大顶堆出堆

特性

树是一对多的数据结构，从一个根结点开始，生长出它的子结点，而每一个子结点又生长出各自的子结点，成为子树。如果某个结点不再生长出子结点了，它就成为叶子。二叉树每个结点最多只有两棵子树，而且左右子树是有顺序的，不可颠倒。满二叉树的所有分支结点都既有左子树又有右子树，并且所有叶子都在同一层。完全二叉树不一定是满的，但它自上而下，自左而右来看的话，是连续没有缺失的。二叉堆是完全二叉树或者近似完全二叉树，父结点的值总是大于或等于(小于或等于)任何一个子节点的值。存储为一维数组，子i父(i-1)/2，父i子2i+1和2i+2入堆，末尾添加，尾元素比较上浮出堆，首尾互换，首元素比较下沉，尾元素出堆

实现

public static void heapSort(int[] arr) { if (arr == null || arr.length == 0) return; int length = arr.length; for (int i = length / 2 - 1; i >= 0; i--) { // 从最后一个元素的父开始整理，建立大顶堆 adjustMaxHeap(arr, i, length); } for (int i = length - 1; i > 0; i--) { // 堆出队列，首尾互换，最大置尾，堆调整 exchange(arr, 0, i); adjustMaxHeap(arr, 0, i); } } private static void adjustMaxHeap(int[] arr, int start, int end) { int temp = arr[start]; int child = start * 2 + 1; // 左边子 while (child < end) { if ((child + 1) < end && arr[child] < arr[child + 1]) { // 两子节点比较选大 child++; // 右边子 } if (arr[child] <= temp) break; // 已是大顶堆 // 否则父沉子浮 arr[start] = arr[child]; // 再循环调整 start = child; child = start * 2 + 1; } arr[start] = temp; }

直接插入排序

分序列为左有序右无序，从第二个数开始向后循环，与有序序列循环比较大小确定位置插入

特性

如果序列基本有序或者长度较小时，使用直接插入排序效率就非常高

实现

public static void insertSort(int[] arr) { if (arr == null || arr.length == 0) return; int insertNum; int length = arr.length; for (int i = 1; i < length; i++) { insertNum = arr[i]; // 无序序列第一个数，即需要插入的数 int j = i - 1; // 有序序列最后位置 while (j >= 0 && arr[j] > insertNum) { // 大则后移 arr[j + 1] = arr[j]; j--; } arr[j + 1] = insertNum; } }

二分插入排序

分序列为左有序右无序，从第二个数开始向后循环，在有序序列中二分查找确定位置插入

实现

public static void binarySort(int[] arr) { if (arr == null || arr.length == 0) return; int insertNum; int length = arr.length; for (int i = 1; i < length; i++) { insertNum = arr[i]; // 无序序列第一个数，即需要插入的数 // 二分查找 int left = 0; // 插入位置 int right = i - 1; // 有序序列最后位置 for (int middle; left <= right; ) { middle = left + (right - left) / 2; if (arr[middle] < insertNum) { left = middle + 1; } else if (arr[middle] > insertNum) { right = middle - 1; } else { left = middle + 1; break; } } // 批量后移 for (int j = i - 1; j >= left; j--) { arr[j + 1] = arr[j]; } arr[left] = insertNum; } }

希尔排序

增量分组，组内插入排序，然后增量二分缩减再插入排序，最后循环缩减增量至一

特性

时间复杂度可以达到O(n^1.3)

实现

public static void shellSort(int[] arr) { if (arr == null || arr.length == 0) return; for (int step = arr.length / 2; step >= 1; step /= 2) { // 增量分组 for (int i = 0; i < step; i++) { // 组内插入排序 insertSort(arr, step); } } } private static void insertSort(int[] arr, int step) { int insertNum; int length = arr.length; for (int i = step; i < length; i += step) { insertNum = arr[i]; // 无序序列第一个数，即需要插入的数 int j = i - step; // 有序序列最后一个数 while (j >= 0 && arr[j] > insertNum) { // 大则后移 arr[j + step] = arr[j]; j -= step; } arr[j + step] = insertNum; } }

快速排序

确定首数为基准数比较大小，从右往左循环小数换位，从左往右循环大数换位，循环至中间相遇位置置为基准数，最后以中间位置分左右两个序列递归

实现

public static void quickSort(int[] arr) { if (arr == null || arr.length == 0) return; quickSort(arr, 0, arr.length - 1); } private static void quickSort(int[] arr, int start, int end) { if (start >= end) return; int baseNumber = arr[start]; // 基准数 int left = start, right = end; while (left < right) { while (left < right && arr[right] >= baseNumber) right--; // 右边寻找小与基准数 if (left < right) arr[left++] = arr[right]; // 小数左移 while (left < right && arr[left] <= baseNumber) left++; // 左边寻找大于基准数 if (left < right) arr[right--] = arr[left]; // 大数右移 } arr[left] = baseNumber; // 基准赋值 // 分开递归 quickSort(arr, start, left - 1); quickSort(arr, left + 1, end); }

归并排序

二分序列归并排序，最后比较大小合并

特性

使用了递归分治的思想，先递归划分子问题，然后合并结果

实现

public static void mergeSort(int[] arr) { if (arr == null || arr.length == 0) return; mergeSort(arr, 0, arr.length - 1); } private static void mergeSort(int[] arr, int start, int end) { if (start >= end) return; // 二分递归 int middle = (start + end) / 2; mergeSort(arr, start, middle); mergeSort(arr, middle + 1, end); merge(arr, start, middle, end); // 合并 } private static void merge(int[] arr, int start, int middle, int end) { int left = start, right = middle + 1; int length = end - start + 1; int[] temp = new int[length]; // 临时数组 // 存入临时数组 int index = 0; while (left <= middle && right <= end) { // 左右两数组比较，小的存入 temp[index++] = arr[left] <= arr[right] ? arr[left++] : arr[right++]; } // 剩下的存入临时数组 while (left <= middle) { temp[index++] = arr[left++]; } while (right <= end) { temp[index++] = arr[right++]; } // 还原 for (int i = 0; i < length; i++) { arr[start + i] = temp[i]; } }

计数排序

序列的值作为计数数组的下标，统计每个数字的个数，最后依次输出计数数组的下标

特性

待排序的数要满足一定的范围的正整数计数排序需要比较多的辅助空间时间复杂度为O(n)

实现

public static void countSort(int[] arr) { if (arr == null || arr.length == 0) return; // 以值为脚标建立计数数组 int max = 0; for (int item : arr) { if (item > max) max = item; } // 映射分配，排序 int[] count = new int[max + 1]; Arrays.fill(count, 0); for (int i : arr) { count[i]++; } // 还原 int index = 0; for (int i = 0; i <= max; i++) { for (int j = 0; j < count[i]; j++) { arr[index++] = i; } } }

桶排序

序列分别映射至有序的桶，桶内排序，最后依次输出

特性

映射函数：关键字k1 < k2，那么f(k1) <= f(k2)，即桶(i)最大的数小于桶(i+1)中最小的数桶越多，桶内需排序的数则越少，单占用空间越大

实现

public static void bucketSort(int[] arr) { if (arr == null || arr.length == 0) return; // 创建桶，使用链表 int bucketNumber = 10; List<List<Integer>> buckets = new ArrayList<>(); for (int i = 0; i < bucketNumber; i++) { buckets.add(new LinkedList<Integer>()); } // 映射分配 int index; for (int item : arr) { index = item / bucketNumber; // 映射关系 buckets.get(index).add(item); } // 排序，还原 index = 0; for (List<Integer> bucket : buckets) { if (!bucket.isEmpty()) { Collections.sort(bucket); // 桶内排序 for (Integer integer : bucket) { arr[index++] = integer; // 还原 } } } }

基数排序

序列按最大位数分趟，按进制分桶，按位的值映射至桶，再依次输出，最后趟循环

特性

多关键字分成多趟单关键字，单关键字排序，最后趟循环

实现

public static void radixSort(int[] arr) { if (arr == null || arr.length == 0) return; // 确定趟数，趟数为最大位数 int max = 0; for (int item : arr) { int length = Integer.toString(item).length(); if (length > max) max = length; } // 创建桶，桶数为进制数 int bucketNumber = 10; List<List<Integer>> buckets = new ArrayList<>(); for (int i = 0; i < bucketNumber; i++) { buckets.add(new LinkedList<Integer>()); } // 按趟排序 int index; for (int i = 0; i < max; i++) { // 映射分配，排序 for (int item : arr) { // 映射关系，按位获取 String s = Integer.toString(item); index = 0; if (s.length() > i) { index = s.charAt(s.length() - i - 1) - '0'; } buckets.get(index).add(item); } // 还原 index = 0; for (List<Integer> bucket : buckets) { if (!bucket.isEmpty()) { for (Integer integer : bucket) { arr[index++] = integer; } } bucket.clear(); } } }