目录

1、概述2、排序算法2.1、冒泡排序2.2、简单选择排序2.3、直接插入排序2.4、希尔排序算法2.5、堆排序2.6、快速排序算法 3、算法的各项指标

1、概述

排序这一章主要是讲解了常用的一些算法，我们在选择用何种排序算法的时候可以根据时间复杂度来判断，文末会给出一个算法的时间及空间复杂度的表，方便决策。

2、排序算法

2.1、冒泡排序

主要是分为三个版本，初级版，改进1，改进2。我们在实际应用时，直接使用改进2即可。

初级版：

/** * 冒泡排序初级版本 * 相邻比较 * * @param arr */ private static void bubbleSort(int[] arr) { int len = arr.length; for (int i = 0; i < len; i++) { for (int j = i + 1; j < len; j++) { if (arr[i] > arr[j]) {//>升序 <降序 swap(arr, i, j); } } } }

冒泡排序改进版1：

/** * 冒泡排序改进版1 * * @param arr */ private static void bubbleSort1(int[] arr) { int len = arr.length - 1; for (int i = 0; i <= len; i++) { for (int j = len - 1; j >= i; j--) { if (arr[j] > arr[j + 1]) {//>升序 <降序 swap(arr, j, j + 1); } } } }

冒泡排序改进版2：

/** * 冒泡排序改进版2 * 时间复杂度最好的是O（n）最差是O(n*n) * * @param arr */ private static void bubbleSort2(int[] arr) { int len = arr.length - 1; boolean isExchange = true; for (int i = 0; i <= len && isExchange; i++) { isExchange = false; for (int j = len - 1; j >= i; j--) { if (arr[j] > arr[j + 1]) {//>升序 <降序 swap(arr, j, j + 1); isExchange = true; } } } }

2.2、简单选择排序

/** * 简单选择排序 * 时间复杂度最好的是O（0）最差是O(n*n) */ private static void selectSort(int[] arr) { int len = arr.length; int i, j, min; for (i = 0; i < len; i++) { min = i; for (j = i + 1; j < len; j++) { if (arr[min] > arr[j]) { min = j; } } if (i != min) { swap(arr, i, min); } } }

2.3、直接插入排序

/** * 直接插入排序 * 时间复杂度最差是O(n*n) */ private static int[] insertSort(int[] arr) { //添加哨兵 int[] sentinelArr = addSentinel(arr); int i, j; int len = sentinelArr.length; for (i = 2; i < len; i++) { if (sentinelArr[i] < sentinelArr[i - 1]) { sentinelArr[0] = sentinelArr[i]; for (j = i - 1; sentinelArr[j] > sentinelArr[0]; j--) { sentinelArr[j + 1] = sentinelArr[j]; } sentinelArr[j + 1] = sentinelArr[0]; } } //移除哨兵 其实也可以不移除，但是结果需要从1开始打印。 int[] resultArr = removeSentinel(sentinelArr); return resultArr; } private static int[] removeSentinel(int[] arr) { int array[] = new int[arr.length - 1]; for (int i = 0; i < arr.length - 1; i++) { array[i] = arr[i + 1]; } return array; } private static int[] addSentinel(int[] arr) { int arraySentinel[] = new int[arr.length + 1]; for (int i = 0; i < arr.length; i++) { arraySentinel[i + 1] = arr[i]; } return arraySentinel; }

2.4、希尔排序算法

/** * 希尔排序算法 */ private static int[] shellSort(int[] arr) { //添加哨兵 int[] sentinelArr = addSentinel(arr); int i, j; int increment = sentinelArr.length; do { increment = increment / 3 + 1;//增量序列选取规则：2的t减k加1次方 后 减1 for (i = increment + 1; i < sentinelArr.length; i++) { if (sentinelArr[i] < sentinelArr[i - increment]) { sentinelArr[0] = sentinelArr[i]; for (j = i - increment; j > 0 && sentinelArr[0] < sentinelArr[j]; j -= increment) { sentinelArr[j + increment] = sentinelArr[j]; } sentinelArr[j + increment] = sentinelArr[0]; } } } while (increment > 1); //移除哨兵 其实也可以不移除，但是结果需要从1开始打印。 int[] resultArr = removeSentinel(sentinelArr); return resultArr; }

2.5、堆排序

/** * 堆排序 * * @param arr */ private static void heapSort(int[] arr) { int i; int len = arr.length - 1; int halfLen = len / 2; for (i = halfLen; i >= 0; i--) { heapAdjust(arr, i, len); } for (i = len; i >= 1; i--) { swap(arr, 0, i); heapAdjust(arr, 0, i - 1); } } private static void heapAdjust(int[] arr, int s, int m) { int temp, j; temp = arr[s]; for (j = 2 * s; j <= m; j *= 2) { if (j < m && arr[j] < arr[j + 1]) { ++j; } if (temp >= arr[j]) { break; } arr[s] = arr[j]; s = j; } arr[s] = temp; }

2.6、快速排序算法

/** * 快速排序算法 */ private static void quickSort(int[] arr) { qSort(arr, 0, arr.length - 1); } private static void qSort(int[] arr, int low, int high) { int pivot; if (low < high) { pivot = partition(arr, low, high); qSort(arr, low, pivot - 1); qSort(arr, pivot + 1, high); } } private static int partition(int[] arr, int low, int high) { int pivotKey; pivotKey = arr[low]; while (low < high) { while (low < high && arr[high] >= pivotKey) { high--; } swap(arr, low, high); while (low < high && arr[low] <= pivotKey) { low++; } swap(arr,low,high); } return low; }

3、算法的各项指标

如下表所示：

排序方法平均情况最好情况最坏情况辅助空间稳定性冒泡排序O(n²)O(n)O(n²)O(1)稳定简单选择排序O(n²)O(n²)O(n²)O(1)稳定直接插入排序O(n²)O(n)O(n²)O(1)稳定希尔排序O(nlogn) ~ O(n²)O(n的1.3次方)O(n²)O(1)不稳定堆排序O(nlogn)O(nlogn)O(nlogn)O(1)不稳定快速排序O(nlogn)O(nlogn)O(n²)O(nlogn) ~O(n)不稳定

全书已完。

---

码字不易，求个关注。

微信公众号： 一粒尘埃的漫旅

里面有很多想对大家说的话，就像和朋友聊聊天。 写代码，做设计，聊生活，聊工作，聊职场。 我见到的世界是什么样子的？ 搜索关注我吧。