好长时间不复习，都快忘了，最近打算重新捡回来。而且偶然发现菜鸟教程现在都已经有算法排序了。
而且，这个动图讲解的确实不错。
菜鸟教程算法排序：https://www.runoob.com/w3cnote/ten-sorting-algorithm.html
这里直接拿来用了，嘿嘿。
排序算法的稳定性
通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。在简单形式化一下，如果Ai = Aj, Ai原来在位置前，排序后Ai还是要在Aj位置前
冒泡排序
冒泡排序，还是简单的，每个人初学c语言的时候一般都会接触到。
它正如名字一样，按照顺序，像泡泡一般一个位置一个位置的变化，直到排序完成。
冒泡排序是稳定的排序算法。
示例
按照从小到大的要求对 3 , 9 , -1, 10, -5
在第一趟中，选出最大的那个
3 比9 小，位置不变=> 3 , 9 , -1, 10, -5
9 比 -1 大，位置变化=>3 , -1 , 9, 10, -5
9 比 10 小，位置不变=>3 , -1 , 9, 10, -5
10 比 -5 大，位置变化=>3 , -1 , 9, -5, 10
所以第一趟的结果位：3 , -1 , 9, -5, 10
接下来进行第二趟：选出第二大那个
3 比 -1 大，位置变化=>-1 , 3 , 9, -5, 10
3 比 9小，位置不变=>-1 , 3 , 9, -5, 10
9 比 -1 大，位置变化=>-1 , 3 , -5, 9, 10
到这里就没必要再比教9和10了，因为第一趟中我们就知道了10已经是最大了！！！
现在我们也知道，9是第二大了
接下来第三趟，找出第三大的那个数
-1比3小，位置不变=>-1 , 3 , -5, 9, 10
3 比 -5大，位置变化=>-1 , -5 , 3, 9, 10
接下里第四趟，找出第四大的数
-1 比 -5 大，位置变化=>-5, -1 , 3, 9, 10
结束！
代码实现
public static void main(String[] args) {int arr[] = {3, 9, -1, 10, -5};//临时变量int temp = 0;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]) {flag = true;temp = arr[j + 1];arr[j + 1] = arr[j];arr[j] = temp;}}System.out.println("第"+ (i + 1) +"趟排序: "+ Arrays.toString(arr));}}
不过，我们对以上代码还可以优化一下。想一下，如果在循环结束前，我们再一次排序中，位置根本就没发送变化，那是不是就代表我们已经排好序了，但是由于循环的原因，我们还得继续比较，其实这是没必要的。
举个极端的例子就是，我现在需要对：1，2，3，4，5来排序，我们只需要在第一趟中确定根本没位置变化就可以退出循环啦。
优化代码：
public static void main(String[] args) {int arr[] = {3, 9, -1, 10, -5};//临时变量int temp = 0;for (int i = 0; i < arr.length - 1; i++) {//标识本次循环是否有交换，如果没有交换，说明已经排好序了，我们没必要往下继续执行，可以直接退出boolean flag = false;for (int j = 0; j < arr.length - 1 - i; j++) {if (arr[j] > arr[j + 1]) {flag = true;temp = arr[j + 1];arr[j + 1] = arr[j];arr[j] = temp;}}System.out.println("第"+ (i + 1) +"趟排序: "+ Arrays.toString(arr));if (!flag) {break;}}
选择排序
选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。每次都会找到未排序元素中的最小值，然后与未排序元素的第一个元素交换位置。
选择排序和冒泡排序相比，减少了交换次数，虽然两个排序都是O(n^2)，但是，选择排序可能稍微快一些。
示例
现在有一个数组 [101,34,119,1]
每一轮都要，遍历数组找出最小值。
第一轮：
从第0个元素开始，认为第0个元素 101 为最小值（min = 101），然后
101与34 比较， min = 34
34 与119比较，min=34
1与34比较，min = 1
现在我们已经找到了最小值为1，并知道了它的下标为3。
现在我们可以讲 101 与 1交换位置，数组变为：[1, 34, 119, 101]
第二轮
从第一个元素开始，min= 34
34 与119比较，min=34
34 与101比较， min = 34
数组位置不变。但我们已经知道了第二个最小值，[1, 34, 119, 101]
第三轮
从第二个元素开始，假定min = 119。
119 与 101 比较，min = 101。
101 与
位置发送变化，[1，34，101，119]
代码实现
public static void main(String[] args) {//选择排序的例子[101,34,119,1]，时间复杂度也是 o(n^2)int[] arr = {101, 34, 119, 1};for (int i = 0; i < arr.length - 1; i++) {//假定 i 为最小值。int minindex = i;int min = arr[i];for (int j = i + 1; j < arr.length; j++) {//如果我们假定的最小值并非最小的话，记录值和下标if (min > arr[j]){min = arr[j];minindex = j;}}//现在 minidex 已经是最小的了if (minindex != i) {arr[minindex] = arr[i];//min 就是最小的值arr[i] = min;}System.out.println("第"+(i + 1) + "轮排序后~：" + Arrays.toString(arr));}}
插入排序
将第一待排序序列第一个元素看做一个有序序列
把第二个元素到最后一个元素当成是未排序序列。
从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。
示例
还是上边的老数据，101, 34, 119, 1
我们可以使用两个数组，这样讲解起来简单，也可以使用一个数组，思想其实都一样，只不过两个数组更容易理解。
我们来看看一个个数组的情况下
arr 101, 34, 119, 1
下标为0的元素，无需比较，所以我们直接从下标为1的元素开始。
我们这里可以用第三方变量 insetVal保存一下 插入的值。，用insertIndex表示要插入的下标
第一轮 i =1，
现在有序序列为101
未排序序列为34，119，1
insetVal = 34，insertIndex为0（这里是假定的，并不一定是这个值，我们接下来还要判断，但是，第一轮毫无疑问就是0）
判断，34和101，34比101小，所以数组arr要进行的操作为，101往后移，arr[insertIndex + 1] = arr[insertIndex];
这个时候其实数组变为了 101,101,119,1
我们还要把将我的34 放到到下标为0的位置，最后数组变为了 0，101，119，1
第二轮
现在有序序列为34，101
未排序序列为119，1
insetVal = 119，insertIndex为1
比较101和119，发现119比101大，我们不用移动元素。直接下一轮
第三轮
现在有序序列为34，101，119
未排序序列为1
insetVal = 1，insertIndex为2
比较119和1，1小， 元素后移，数组变为 34，101，119，119，inserIndex—变为1
比较101和1，1小，元素后移，数组变为34，101，101，119，insertIndex—变为0
比较34和1，1小，元素后移，数组变为34，34，101，119，insertIndex—变为-1
最后将1放入到0元素的位置
arr[insertIndex + 1] = insertVal，数组变为1，34，101，119
代码实现
public static void main(String[] args) {int[] arr = {101, 34, 119, 1};//插入排序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[i] 这个值，这个值已经被我们备份到 insertVal了arr[insertIndex + 1] = arr[insertIndex];insertIndex--;}//只要运行到这里，说明我们的数组中已经找到了要插入的位置了arr[insertIndex + 1] = insertVal;System.out.println("第"+ i + "轮插入排序后~: " + Arrays.toString(arr));}}
希尔排序
希尔也是不稳定的排序。
希尔排序实际上是基于插入排序的一种更优化的排序算法。
希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录”基本有序”时，再对全体记录进行依次直接插入排序。
示例
第一次 gap = length / 2=5,于是将数据分为5组，分别是[8，3]，[9，5]，[1，4]，[7，6]，[2，0]
8与3比较
gap = 5, arr的情况~:[3, 9, 1, 7, 2, 8, 5, 4, 6, 0]
9与5比较
gap = 5, arr的情况~:[3, 5, 1, 7, 2, 8, 9, 4, 6, 0]
1与4比较
数组不用发生变化
7与6比较
gap = 5, arr的情况~:[3, 5, 1, 6, 2, 8, 9, 4, 7, 0]
2与0比较
gap = 5, arr的情况~:[3, 5, 1, 6, 0, 8, 9, 4, 7, 2]
第二趟 gap = 5 /2 =2时。将数据分为2组，[3，1，0，9，7]，[5，6，8，4，2]
3与1比较
gap = 2, arr的情况~:[1, 5, 3, 6, 0, 8, 9, 4, 7, 2]
5与6比较
数组不用发生变化
3与0比较
gap = 2, arr的情况~:[0, 5, 1, 6, 3, 8, 9, 4, 7, 2]
6与8比较
数组不用发生变化
3与9比较
数组不用发生变化
8与4比较
gap = 2, arr的情况~:[0, 4, 1, 5, 3, 6, 9, 8, 7, 2]
9与7比较
gap = 2, arr的情况~:[0, 4, 1, 5, 3, 6, 7, 8, 9, 2]
8与2比较
gap = 2, arr的情况~:[0, 2, 1, 4, 3, 5, 7, 6, 9, 8]
0与2比较
数组不用发生变化
最后一次 gap = 1，进行最后一次插入排序
2与1比较
gap = 1, arr的情况~:[0, 1, 2, 4, 3, 5, 7, 6, 9, 8]
2与4比较
数组不用发生变化
4与3比较
gap = 1, arr的情况~:[0, 1, 2, 3, 4, 5, 7, 6, 9, 8]
4与5比较
数组不用发生变化
5与7比较
数组不用发生变化
7与6比较
gap = 1, arr的情况~:[0, 1, 2, 3, 4, 5, 6, 7, 9, 8]
7与9比较
数组不用发生变化
9与8比较
gap = 1, arr的情况~:[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
代码
public static void main(String[] args) {//希尔排序，本质上也是一种插入排序，只不过进行了分组，每次都利用前一次排好序的数据，交换次数更少。int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};//多少个一组，现在有10个数，第一次 分成5组，第二次分成2组，最后分为1组也就是排好序的值for (int gap = arr.length / 2; gap > 0; gap = gap / 2) {for (int i = gap; i < arr.length; i++) {int j = i;int temp = arr[i];//当 j-gap 位置的数 比 j大的时候才开始插入排序if (arr[j - gap] > temp) {//找到要插入的位置，并且在插入的过程中后移。while (j - gap >= 0 && arr[j - gap] > temp) {//数据整体向后移arr[j] = arr[j - gap];//继续向前遍历j = j -gap;}//到这里时，已经找到了最小值的位置,直接插入。arr[j] = temp;System.out.println("gap = " + gap + ", arr的情况~:" +Arrays.toString(arr));}}}}
快速排序
快排基于冒泡，它是一种不稳定的排序，快的时候很快，慢的时候又等于冒泡
1、先从数列中取出一个数作为基准数，可以选择默认从0开始。
2、有两个指针low指向队首，high指向队尾， low++向后移找到比基准数大的值，找到后交换位置arr[high] = arr[low]，high—找到比基准数小的，找到后交换位置arr[low] = arr[high]，如果找到了就交换位置，否则就一直遍历，知道low>=high 退出循环。
3、重复步骤2，直到位置有序
示例
23, 46, 0, 8, 11
temp 为基准数 23
low = 0，high = 4
先从后边开始遍历，11比基准数小，符合我们要交换的条件，直接arr[low] = arr[high]
数组现在变为 11，46，0，8，11。
再从前边开始遍历，11不符合条件，low++ 变为1，46比23大，符合交换条件，arr[high] = arr[low]
数组变为11，46，0，8，46
现在 low =1，high=4
从后边开始遍历，46比23大，high—变为3，8比23小，交换，数组变为11，8，0，8，46
low=1，high=3
从前边开始遍历，8比23小，low++变成2，0比23小low++变成3。
现在low = high了已经不符合遍历条件了，此时相当于我们找到了基准数应处于的下标位置index = 3
我们就直接arr[low] = temp,数组变为 11，8，0，23，46
现在第一遍完成了。
将下列代码向左递归，向右递归。直到排好序
quickSort(arr, low, index - 1);
quickSort(arr, index + 1, high);
代码
public static void main(String[] args) {int[] arr = {23, 46, 0, 8, 11};quickSort(arr, 0, arr.length - 1);System.out.println("排序后:");for (int i : arr) {System.out.println(i);}}private static void quickSort(int[] arr, int low, int high) {if (low < high) {// 找寻基准数据的正确索引int index = getIndex(arr, low, high);// 进行迭代对index之前和之后的数组进行相同的操作使整个数组变成有序quickSort(arr, low, index - 1);quickSort(arr, index + 1, high);}}private static int getIndex(int[] arr, int low, int high) {// 基准数据int tmp = arr[low];while (low < high) {// 当队尾的元素大于等于基准数据时,向前挪动high指针while (low < high && arr[high] >= tmp) {high--;}// 如果队尾元素小于tmp了,需要将其赋值给lowarr[low] = arr[high];// 当队首元素小于等于tmp时,向前挪动low指针while (low < high && arr[low] <= tmp) {low++;}// 当队首元素大于tmp时,需要将其赋值给higharr[high] = arr[low];}// 跳出循环时low和high相等,此时的low或high就是tmp的正确索引位置// 由原理部分可以很清楚的知道low位置的值并不是tmp,所以需要将tmp赋值给arr[low]arr[low] = tmp;return low; // 返回tmp的正确位置}
归并排序
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。
对并排序将一组数据不断拆分拆分再拆分，一直到最后不能拆分为止。然后用最小的单位进行排序合并。
它稳定的排序算法。
示例
以图中为例（注意是递归思想，先左递归后右递归）
8，4，5，7，1，3，6，2
分为
8，4，5，7 和 1，3，6，2
8，4，5，7分为
8，4和5，7
8，4 分为 8和4
这已经不能再分了，于是开始合并
8和4合并为 4，8
5，7分为5和7
开始合并
5和7合并为5，7
4，8 和 5，7 合并为 4，5，7，8
1，3，6，2分为
1，3和6，2
1，3分为 1和3
开始合并 为1，3
6，2分为，6，2
开始合并 2，6
1，3 和2，6合并为1，2，3，6
1，2，3，6 和 4，5，7，8合并为
1，2，3，4，5，6，7，8
代码
public static void main(String[] args) {//归并排序int[] arr = {8, 4, 5, 7, 1, 3, 6, 2};int[] temp = new int[arr.length];mergeSort(arr, 0, arr.length - 1, temp);System.out.println(Arrays.toString(arr));System.out.println(Arrays.toString(temp));}//分解+合并public static void mergeSort(int[] arr, int left, int right, int[] temp) {//如果 left >= right，不符合我们的递归条件if (left < right) {//先获取 midint 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 中间索引(left + right)/ 2* @param right 右边有序序列的索引* @param temp 第三方做中转数组*/public static void merge(int[] arr, int left,int mid, int right, int[] temp) {int i = left; //左边序列的下标指针int j = mid + 1;//右边序列下标指针int t = 0; //temp的下标指针//将左右两边的有序数据按照规则填充到temp数组while (i <= mid && j <= right) {//如果 左边的小，就放入到temp中，然后i++//两者都要进行t++if (arr[i] <= arr[j]) {temp[t++] = arr[i++];}else {//如果 右边的小，就放入到temp中，然后j++temp[t++] = arr[j++];}}//运行到这，进行过数组合并的同学肯定都知道最后总会有一方，剩余，接下来就将剩余部分全部填充到数组。//如果左边剩余while (i <= mid) {temp[t++] = arr[i++];}//如果右边剩余while (j <= right) {temp[t++] = arr[j++];}System.out.println(Arrays.toString(temp));//现在我们的temp中的数据已经是有序的了，那么我们还要将其赋值到arr中t = 0;int tempIndex = left;while (tempIndex <= right) {arr[tempIndex++] = temp[t++];}}
基数排序
基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。
如果在处理十位的时候，被排序的数只有个位，比如9，那么前边要补零09，它十位视为0
示例
arr = [53, 3, 542, 748, 14, 214]
第一轮：
2桶：：：[542]
3桶：：：[53, 3]
4桶：：：[14, 214]
8桶：：：[748]
取出后 arr[542, 53, 3, 14, 214, 748]
第二轮：
0桶：：：[3]
1桶：：：[14, 214]
4桶：：：[542, 748]
5桶：：：[53]
取出后 arr [3, 14, 214, 542, 748, 53]
第三轮：
0桶：：：[3, 14, 53]
2桶：：：[214]
5桶：：：[542]
7桶：：：[748]
取出后 arr [3, 14, 53, 214, 542, 748]
代码
public static void main(String[] args) {//基数排序int[] arr = {53, 3, 542, 748, 14, 214};//定义一个二维数组用来表示10个桶，分别是0-9,列坐标为存入的值//其实这个用队列（链表）来做会更好。int[][] bucket = new int[10][arr.length];//为了确定每个桶数组存放多少数据，我们不得不搞一个一维数组来记录下个数int[] bucketCount = new int[10];//在排序之前我们还必须找到最大的数到底是几位int max = arr[0];for (int i = 0; i < arr.length; i++) {if (arr[i] > max) {max = arr[i];}}int maxLenth = (max + "").length();//接下来我们要进行桶排序了for (int i = 0, n = 1; i < maxLenth; i++, n*=10) {for (int j = 0; j < arr.length; j++) {//找出位数上的数值int digit = arr[j] / n % 10;//放入到对应的桶中,桶的有效位数+1bucket[digit][bucketCount[digit]++] = arr[j];}//然后将桶中的值依次取出来，放入到arr中//用来代表 arr 的下标int index = 0;for (int j = 0; j < bucketCount.length ; j++) {//如果等于0我们根本无需遍历if (bucketCount[j] != 0) {for (int k = 0; k < bucketCount[j]; k++) {arr[index++] = bucket[j][k];}}//记得将桶的有效位下标给清空bucketCount[j] = 0;}}System.out.println(Arrays.toString(arr));}
各算法时间复杂度和稳定性总结
若有收获，就点个赞吧
0 人点赞
