〇、排序算法简介
排序：将一组数据依照指定的程序进行排列的过程。
排序的分类：
- 外部排序：将须要解决的所有数据加载到内存中进行排序。
- 内部排序：因为数据量过大无奈全副加载到内存中，须要借助外存进行排序。
咱们钻研的排序算法次要是外部排序算法。其中外部排序又能够分为冒泡排序、简略抉择排序（简称为抉择排序）、间接插入排序（简称为插入排序）、希尔排序、疾速排序、归并排序、基数排序、堆排序八大排序算法：
本篇将介绍冒泡排序、抉择排序、插入排序、疾速排序。下篇将介绍希尔排序、归并排序、基数排序、堆排序。
一、冒泡排序
根本思维：看待排序序列从前向后，顺次比拟相邻元素的值，若发现逆序则替换，使值较大的元素逐步从前移向后部，就象水底下的气泡一样逐步向上冒。
对于待排序数组[3, 9, -1, 10, 20]，冒泡排序算法的图解过程如下：
由此能够写出冒泡排序算法的代码：
public static void bubbleSort(int[] arr) { for (int i = 0; i < arr.length - 1; i++) { for (int j = 0; j < arr.length - 1 - i; j++) { if (arr[j] > arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } }}该代码能够优化：
public static void bubbleSort(int[] arr) { for (int i = 0; i < arr.length - 1; i++) { int temp; boolean flag = false; for (int j = 0; j < arr.length - 1 - i; j++) { if (arr[j] > arr[j + 1]) { flag = true; temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } if (!flag) { //优化 break; } }}二、抉择排序
根本思维：从待排序的数据中，按指定的规定选出某一元素，再依规定替换地位，达到排序。
对于待排序数组[3, 9, -1, 10, 20]，抉择排序算法的图解过程如下：
由此能够写出抉择排序算法的代码：
public static void selectSort(int[] arr) { for (int i = 0; i < arr.length - 1; i++) { int minIndex = i; for (int j = i + 1; j < arr.length; j++) { if (arr[minIndex] > arr[j]) { minIndex = j; } } if (minIndex != i) { int temp = arr[minIndex]; arr[minIndex] = arr[i]; arr[i] = temp; } }}三、插入排序
根本思维：对于待排序的元素，以插入的形式寻找该元素的适当地位，达到排序。
对于待排序数组[3, 9, -1, 10, 20]，插入排序算法的图解过程如下：
由此能够写出插入排序算法的代码：
public static void insertSort(int[] arr) { for (int i = 1; i < arr.length; i++) { int insert = arr[i]; int j; for (j = i - 1; j >= 0; j--) { if (insert < arr[j]) { arr[j + 1] = arr[j]; } else { break; } } arr[j + 1] = insert; }}该代码能够优化：
public static void insertSort(int[] arr) { for (int i = 1; i < arr.length; i++) { int insertVal = arr[i]; int insertIndex = i - 1; while (insertIndex >= 0 && insertVal < arr[insertIndex]) { arr[insertIndex + 1] = arr[insertIndex]; insertIndex--; } if (insertIndex + 1 == i) { //优化 arr[insertIndex + 1] = insertVal; } }}四、疾速排序
根本思维：首先设定一个分界值（主元），通过一趟排序（划分函数），将待排序数组宰割成两局部，其中一部分的所有元素都比另外一部分的所有元素要小，而后再按此办法对这两局部数据别离进行疾速排序，整个排序过程能够递归进行，以此达到整个数据变成有序序列。
主元的选取：主元能够抉择首元素、尾元素、两头元素、随机选取、三点中值法、相对中值法等。抉择首元素作为主元往往是不通过充分考虑的。但为了不便起见，本篇选取首元素作为主元。
划分函数的选取：划分函数能够抉择单向扫描分区法、双向扫描分区法等。本篇选取双向扫描分区法：选定主元后，确定左右“指针”扫描待排序数组；保障左指针在右指针的右边，当左指针元素不大于主元时一直向右推动，当右指针元素不小于主元时一直向左推动；直到左右指针相交，即为主元的地位。
由此能够写出疾速排序算法的代码：
public static void quickSort(int[] arr, int left, int right) { int l = left; int r = right; int pivot = arr[left]; while (l <= r) { while (l <= r && arr[l] <= pivot) l++; //左指针元素不大于主元时一直向右推动 while (l <= r && arr[r] >= pivot) r--; //右指针元素不小于主元时一直向左推动 if (l <= r) { int temp = arr[l]; arr[l] = arr[r]; arr[r] = temp; } } arr[left] = arr[r]; //arr[r]即为主元的地位 arr[r] = pivot; if (left < r) quickSort(arr, left, r); if (right > l) quickSort(arr, l, right);}