排序算法分类
排序算法依据解决数据应用到的存储设备可分为两大类，别离是外部排序和内部排序。
- 外部排序：将须要解决的数据都加载到内存中进行排序
- 内部排序：因为数据量过于宏大，单靠内存无奈实现，须要借助内部存储进行排序
外部排序又可细分，如下图所示
插入排序
1.间接插入排序
- 基本思路：首先先从数组中抉择一个数x放到一个数组里，从遍历以后数组，和新数组的每一个元素进行比拟，从而决定它放在什么地位，只能以后数组的每个元素都放进去了
- 举个例子，数组{7,5,9,3,12,8,20,18},总共须要7趟，假如咱们抉择7作为第一个数
初始状态：(7),5,9,3,12,8,20,18，从下标1开始找，放到新数组里(7)
第1趟：(5,7),9,3,12,8,20,18
第2趟：(5,7,9),3,12,8,20,18
第3趟：(3,5,7,9),12,8,20,18
第4趟：(3,5,7,9,12),8,20,18
第5趟：(3,5,7,8,9,12),20,18
第6趟：(3,5,7,8,9,12,20),18
第7趟：(3,5,7,8,9,12,18,20)
- 代码如下：
public static void insertSort(int[] arr){ if (arr == null || arr.length <= 0 ) return; int len = arr.length; for (int i = 1; i < len; i ++){ //保留以后地位的值 int insertValue = arr[i]; //找到以后地位的前一个地位 int insertIndex = i - 1; //和前一个地位进行比拟，只有比前一个小，就把前一个地位的值赋给以后地位 //始终循环上来，直到本人成为了第一个数或者找到了一个比本人还小的数 while (insertIndex >= 0 && insertValue < arr[insertIndex]){ arr[insertIndex + 1] = arr[insertIndex]; insertIndex--; } //把之前保留的数和赋给以后找到的地位 arr[insertIndex + 1] = insertValue; } }2.希尔排序
- 基本思路：先将整个待排序的记录宰割成若干子序列，别离对这些子序列进行排序，待整个残缺的序列根本有序时，再对整体记录进行顺次间接插入排序
举个例子：比方对于数组{9,12,8,98,36,29,190,54}
- 1）初始数组如下：
- 2）抉择一个增量gap，通常是数组长度的一半，这里gap取4
- 对同一子序列进行排序，排序后果如下：
- 3）对上一轮排序的后果再次抉择一个重量，gap取上一次gap的一半为2，排序后果如下：
- 4）再次取上一次gap的一半，为1，此时排序的是整个数组，排序后果如下，
- 当gap为1时，整个数组曾经排好序
代码如下：
- 实现希尔排序有两种算法，一种是交换法一种是移位法，前者的效率没有后者的高
public class ShellSort { public static void change(int[] arr, int aIndex, int bIndex){ int temp = arr[aIndex]; arr[aIndex] = arr[bIndex]; arr[bIndex] = temp; } //交换法 public static void sort(int[] arr){ int temp = 0; for (int gap = arr.length/2; gap > 0; gap /= 2){ for (int i = gap; i < arr.length; i++ ){ for (int j = i - gap; j >= 0;j -= gap){ if (arr[j] > arr[j + gap]){ temp = arr[j]; arr[j] = arr[j + gap]; arr[j + gap] = temp; } } } } } //移位法 public static void sort2(int[] arr){ for (int gap = arr.length/2; gap > 0; gap /= 2){ //从第gap个元素，一一对其所在的组进行间接插入排序 for (int i = gap; i < arr.length; i++){ int j = i; int temp = arr[j]; if(arr[j] < arr[j-gap]){ while (j - gap >= 0 && temp < arr[j-gap]){ arr[j] = arr[j - gap]; j -=gap; } arr[j] = temp; } } } } public static void main(String[] args) { int[] arr = {7,5,9,3,12,8,20,18}; sort2(arr); System.out.println(Arrays.toString(arr)); }}抉择排序
1.简略抉择排序
- 基本思路：从数组中找到一个最大数,和数组的最初一个数替换（也能够最小），而后再从第一个开始到倒数第二个找到最大数和倒数第二个数替换，反复这样做，直到只剩一个第一个数，这样整个数组的序就排好了
- 举个例子，数组{7,5,9,3,2,1,12,20},总共须要7趟（数组的长度 - 1）
第一趟：最大数为20，和第7个数替换，7,5,9,3,2,1,12,20
第二趟：最大数为12，和第6个数替换，7,5,9,3,2,1,12,20
第三趟：最大数为9，和第5个数替换，7,5,1,3,2,9,12,20
第四趟：最大数为7，和第4个数替换，2,5,1,3,7,9,12,20
第五趟：最大数为5，和第3个数替换，2,3,1,5,7,9,12,20
第六趟：最大数为3，和第2个数替换，2,1,3,5,7,9,12,20
第七趟：最大数为2，和第1个数替换，1,2,3,5,7,9,12,20
代码如下：
public static int[] selectSort(int[] arr){ if (arr == null || arr.length <= 0 ) return null; int len = arr.length; for (int i = 0; i < len - 1; i ++){ int maxIndex = 0; for (int j = 0; j < len - i; j ++){ if (compare(arr[j], arr[maxIndex])){ maxIndex = j; } } change(arr, maxIndex, len - 1 - i); } return arr; }private static boolean compare(int a, int b){ if (a > b) return true; return false; } private static void change(int[] arr, int a, int b){ int temp = arr[a]; arr[a] = arr[b]; arr[b] = temp; }
2.堆排序
后期常识
- 要理解堆排序，必须晓得堆这种数据结构，堆是一个近似齐全二叉树，这种数据结构有个个性，即子节点的键值或索引总是小于（大于）它的父节点，而堆又分为大项堆和小项堆
- 1）大项堆：每个节点的值都大于或等于其子节点的值
- 2）小项堆：每个节点的值都小于或等于其子节点的值
- 比方：
基本思路
- 1）把待排序的数组构建成一个大根堆，此时最大值就是根元素
- 2）把堆首元素和堆尾元素进行调换，此时最大值就在堆尾
- 3）把堆的第一个元素到堆长度-1个元素进行第一和第二步操作，直到堆的长度为1
举个例子，数组{1,5,9,10,19,8}
- 1）首先找到第一个元素，发现它没有父节点，则不替换
- 2）找到第二个元素5，发现它比父节点的值1还要大，两个元素进行替换
- 3）找到第三个元素9，发现它比父节点的值5还要大，两个元素进行替换
- 4）找到第四个元素10，发现它比父节点的值1还要大，两个元素进行替换，替换之后发现它还是比父节点的值9大，两个元素再进行替换
- 5）找到第五个元素19，发现它比父节点的值9大，两个元素进行替换，替换之后发现它还是比父节点的值10大，两个元素再进行替换
- 6）找到第六个元素8，发现它比父节点的值5大，两个元素进行替换
- 7）上述6步骤把整个数组构建成了大项堆，之后把堆首元素19和堆尾元素5进行替换
- 8）之后再把数组的length - 1个元素构建成大项堆，再次替换，直到要构建的数组的长度只剩一个
- 代码如下
public class HeapSort{ public static void swap(int[] arr, int i, int j){ int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } public static void main(String[] arg){ int[] arr = {1,5,2,4,9,10}; heapSort(arr); System.out.println(Arrays.toString(arr)); } public static void heapSort(int[] arr){ //结构大根堆 int size = arr.length; System.out.println("1）结构大根堆："); heapInsert(arr,0 , size); int i = 1; while (size > 1){ //固定最大值 swap(arr, 0 , size - 1); System.out.print("t第" + i + "次固定最大值："); System.out.println(Arrays.toString(arr)); size --; //结构大根堆 System.out.println((++ i)+"）结构大根堆："); heapify(arr, 0 , size); } } //结构大根堆（通过新插入的数回升） public static void heapInsert(int[] arr, int start, int length){ for (int i = start; i < length; i ++){ //以后插入的索引 int currentIndex = i; //父节点索引 int fatherIndex = (currentIndex - 1)/2; while (arr[currentIndex] > arr[fatherIndex]){ //替换以后节点与父节点的地位 swap(arr, currentIndex, fatherIndex); //从新计算以后节点与父节点的索引 currentIndex = fatherIndex; fatherIndex = (currentIndex - 1) / 2; } System.out.println("t第" + i + "次替换：" + Arrays.toString(arr)); } } //将残余的数结构储层大根堆 public static void heapify(int[] arr, int index, int size){ int left = 2 * index + 1; int right = 2 * index + 2; while (left < size){ int largestIndex = index; //判断孩子中较大的值的索引（确保右孩子在size范畴之内） if (arr[left] < arr[right] && right < size){ largestIndex = right; }else { largestIndex = left; } //比拟父节点的值与孩子中较大的值，并确定最大值的索引 if (arr[index] > arr[largestIndex]){ largestIndex = index; } //如果父节点索引是最大值的索引，那曾经是大根堆了，则推出循环 if (index == largestIndex){ break; } //父节点不是最大值，与孩子中较大的值替换 swap(arr, largestIndex, index); System.out.println("tleft：" + left + "tright：" + right); System.out.println("tindex：" + index); System.out.println("tlargestIndex：" + largestIndex); System.out.println("t替换：" + Arrays.toString(arr)); //将索引指向孩子中较大的值的索引 index = largestIndex; //从新计算替换之后的孩子的索引 left = 2 * index + 1; right = 2 * index + 2; } } }替换排序
1.冒泡排序
- 基本思路：排序从前向后，顺次比拟相邻元素的值，如果前一个元素比后一个元素小，则两个元素调换地位。
- 举个例子：如下数据{3,44,38,5,47,15,36,26,27,2,46,4,19,50,48}
用最根底的办法进行比拟：
第一趟：3,38,5,44,15,36,26,27,2,46,4,19,47,48,50
第二趟：3,5,38,15,36,26,27,2,44,4,19,46,47,48,50
第三趟：3,5,15,36,26,27,2,38,4,19,44,46,47,48,50
第四趟：3,5,15,26,27,2,36,4,19,38,44,46,47,48,50
第五趟：3,5,15,26,2,27,4,19,36,38,44,46,47,48,50
第六趟：3,5,15,2,26,4,19,27,36,38,44,46,47,48,50
第七趟：3,5,2,15,4,19,26,27,36,38,44,46,47,48,50
第八趟：3,2,5,4,15,19,26,27,36,38,44,46,47,48,50
第九趟：2,3,4,5,15,19,26,27,36,38,44,46,47,48,50
第十趟：2,3,4,5,15,19,26,27,36,38,44,46,47,48,50
第十一趟：2,3,4,5,15,19,26,27,36,38,44,46,47,48,50
第十二趟：2,3,4,5,15,19,26,27,36,38,44,46,47,48,50
第十三趟：2,3,4,5,15,19,26,27,36,38,44,46,47,48,50
第十四趟：2,3,4,5,15,19,26,27,36,38,44,46,47,48,50
第十五趟：2,3,4,5,15,19,26,27,36,38,44,46,47,48,50
- 代码实现：
一般来说，有几个数咱们就要循环几趟，然而有的时候其实可能整个数组的程序曾经排序好了，然而可能还剩好几趟，比方下面的例子中，在第十趟的时候其实曾经排号序了。所以在代码实现中，设置一个标记，如果一趟下来都没有两个相邻数之间进行替换，则示意整个数组曾经排好序了，所以间接跳出循环。
public class Bubble { //比拟两个数的大小 public static boolean compare(int a, int b){ if (a > b){ return true; } return false; } //替换两个数的地位 public static void change(int[] arr, int aIndex, int bIndex){ int temp = arr[aIndex]; arr[aIndex] = arr[bIndex]; arr[bIndex] = temp; } public static void sort(int[] arr){ boolean flag = false;//标记位 for (int i = 0; i < arr.length - 1; i++){ for (int j = 0; j < arr.length - i -1;j++){ if (compare(arr[j], arr[j + 1])){ flag = true; change(arr, j, j+1); } } if (!flag){ break; }else { flag = false; } } }}2.疾速排序
- 基本思路：首先找到一个基准数，比这个数大的放到它的右边，比这个数小的放到它的左边，而后再别离对它的左右两边进行雷同的操作，直到左右两边的数都排好序。
- 举个例子：数组arr={12,18,6,9,14,8,4,3,19}，咱们把数组的每一位数设想成一个房间，每个房间里装着一个人
- 令i = 0,j = 8,x=arr[i]; i代表最右边的下标，j代表最左边的下标，x为基准数
- 首先咱们须要对arr进行第一次排序，让x右边全都是比它小的数，x的左边全都是比它大的数，咱们从下标j开始往前查找，咱们先把x从房间里请进去，此时arr[0]的房间是空的（但实际上这个房间还是有人的，这样是为了不便了解）
从后往前找，直到找到比x小的数：咱们发现arr[8]并不大于x，那么令j--,这时咱们发现arr[7]=3是小于x的，那么此时咱们把3赋给arr[0]，这就相当于把房间7的人放到了房间0外面，这时房间7空了，前面的房间空了就须要后面的房间来补
- 此时数组为arr={3,18,6,9,14,8,4,
3,19},i=0,j=7
- 此时数组为arr={3,18,6,9,14,8,4,
从前往后找，直到找到比x大的数：此时arr[0]并不大于x，令i++，发现arr[1]=18大于12，那咱们就能够把房间1的人放到空房间7
- 此时数组为arr={3,
18,6,9,14,8,4,18,19},i=1,j=7
- 此时数组为arr={3,
当初是房间1空了，从后往前找，发现arr[6]=4小于x，把房间6的人放到了房间1
- 此时数组为arr={3,4,6,9,14,8,
4,18,19},i=1,j=6
- 此时数组为arr={3,4,6,9,14,8,
当初是房间6空了，从前往后找，发现arr[4]=14大于x，把房间4的人放到了房间6
- 此时数组为arr={3,4,6,9,
14,8,14,18,19},i=4,j=6
- 此时数组为arr={3,4,6,9,
当初是房间4空了，从后往前找，发现arr[5]小于x，把房间5的人放到了房间6
- 此时数组为arr={3,4,6,9,8,
8,14,18,19},i=4,j=5
- 此时数组为arr={3,4,6,9,8,
当初是房间5空了，从前往后找，发现arr[5]不大于x，并且i和j相等了，那么第一次排序就完结了，站在门外的x进去了房间5
- 此时数组为arr={3,4,6,9,8,12,14,18,19}
- 当初就把12右边的数再进行一次排序，12左边的数再进行一次排序，反复进行直到整个数组排序排好了
代码如下：
public static void quickSort(int[] arr, int start, int end){ //边界条件 if (arr == null || arr.length <= 1 || start >= end) return; //设置基准值x，右边索引i，左边索引j int i = start,j = end; int x = arr[i]; //只有i大于等于j,就始终找 while (i < j){ while (i < j && arr[j] >= x) j --; if (i < j) arr[i] = arr[j]; while (i < j && arr[i] < x) i ++; if (i < j) arr[j] = arr[i]; } arr[i] = x; //左右两边递归排序 quickSort(arr, start, i - 1); quickSort(arr, i + 1, end); }归并排序
基本思路：
- 归并排序是采纳分而治之的思维，将待排序的数组分成若干个数组，对每个数组进行排序，而后再将排序好的数组合并，如下图所示
举个例子：数组{1,4,6,7,9,2,3,5}
- 联合上图，首先对整个数组进行递归等分，直到被合成进去的数组的长度为1，而后对相邻的两个数组进行有序的合并，直到所有扩散的数组合并成一个有序数组
- 合并的步骤：比方上图中的数组{1,4,6,7}和数组{2,3,5,9}的合并，首先左边数组的第一个元素和右边数组的第一个元素进行比拟，如果左边的小则把该元素放到一个长期的数组temp里存着，反过来也是一样。直到左右两边有一边被解决完，而后把残余的另一边的数组填充到temp数组里，这样就合并实现
- 代码如下：
public class Test { public static void main(String[] args) { int arr[] = { 8, 4, 5, 7, 1, 3, 6, 2 }; mergeSort(arr, 0, arr.length - 1, new int[arr.length]); System.out.println(Arrays.toString(arr)); } //分 + 并 public static void mergeSort(int[] arr, int left, int right, int[] temp){ if (left < right){ int mid = (left + right) / 2; //向左递归合成 mergeSort(arr, left, mid, temp); //向右递归合成 mergeSort(arr, mid + 1, right, temp); //合并 merge(arr, left, mid, right, temp); } } //合并的办法 /** * @param arr 待排序的数组 * @param left 右边有序序列的起始索引 * @param mid 两头索引 * @param right 左边有序序列的开端索引 * @param temp 长期存储的数组 */ public static void merge(int[] arr, int left, int mid, int right, int[] temp){ int i = left; //i指向右边有序序列的起始索引 int j = mid + 1; //j指向左边有序序列的起始索引 int t = 0; //t指向temp数组的以后索引 //1）首先，把左右两边的数据填充到temp数组中 //直到左右两边的有序序列有一边曾经处理完毕 while (i <= mid && j <= right){ //如果右边的有序序列的以后元素小于等于左边的，则填充到temp数组，反之亦然 //填充完之后索引值递增 if (arr[i] <= arr[j]){ temp[t] = arr[i ++]; }else { temp[t] = arr[j ++]; } t ++; } //2）把残余一边的有序序列填充到temp数组中 while (i <= mid){//如果右边序列还有残余，则解决 temp[t ++] = arr[i ++]; } while (j <= right){//如果左边序列还有残余，则解决 temp[t ++] = arr[j ++]; } //3）把temp数组的元素拷贝到arr数组 //并不是每次temp数组的总元素都和arr数组相等 t = 0; //初始化temp的起始索引 int tempLeft = left; //获取右边序列的起始索引 while (tempLeft <= right){ arr[tempLeft ++] = temp[t ++]; } } }基数排序
举例说明：比方待排序数组为{53, 42, 9, 4, 128, 64, 989}
- 1）首先，获取所有元素的个位数，依据个位数放入到对应的桶中（桶有10个），而后按序将放入桶中元素拿出赋给原来的数组，则第一趟的后果为：42，53，4，64，128，9，989
- 2）而后获取所有元素的十位数，依据十位数放入到对应的桶中，如果位数不够的主动补0，放入到0号桶中，则第二趟的后果为：4，9，128，42，53，64，989
- 3）最初获取所有元素的百位数，依据百位数放入到对应的桶中，如果位数不够的话也是主动补0，则第三趟的后果为：4，9，42，53，64，128，989
- 留神：趟数和该元素的最大值的位数统一，如果该数组有千位的话还须要进行第四趟，依据千位数进行排序
- 代码如下：
public class RadixSort { public static void main(String[] args) { int arr[] = { 53, 3, 542, 748, 14, 214}; radixSort(arr); } public static void radixSort(int[] arr){ //1、获取arr数组中的最大值的位数 int max = arr[0]; for (int temp : arr){ if (temp > max){ max = temp; } } int maxLength = (max + "").length(); //2、初始化桶、以及每个桶对应的索引 //每个桶的长度为arr的长度（取最坏的状况） int[][] bucket = new int[10][arr.length]; //记录每个桶理论放了多少数据 int[] bucketEleCounts = new int[10]; //3、循环解决桶 for (int i = 0, n = 1; i < maxLength; i ++, n *= 10){ //遍历数组，对每个数组的对应位进行排序解决（从个位数开始） for (int j = 0; j < arr.length; j ++){ //获取该元素的对应位的值 int digit = arr[j] / n % 10; //通过digit，将该元素放入绝对应的桶中 bucket[digit][bucketEleCounts[digit] ++] = arr[j]; } //依照桶的顺组，将每个桶中的数据放入到原来的arr数组中 int index = 0; //记录arr数组以后地位 //遍历每一个桶 for (int k = 0; k < bucketEleCounts.length; k ++){ //如果桶中有数据咱们才放入arr中 int count = bucketEleCounts[k]; if (count != 0){ //循环第k个桶，将数据放入arr中 for (int l = 0; l < count; l ++){ arr[index ++] = bucket[k][l]; } //每一轮解决过后，须要将bucketEleCount清零，为下一轮做筹备 bucketEleCounts[k] = 0; } } System.out.println("第" + (i + 1) + "轮，arr = " + Arrays.toString(arr)); } } }