1. 冒泡排序
来源百度百科:
冒泡排序(Bubble Sort，台湾译为:泡沫排序或气泡排序)是一种简单的排序算法。它重复地走 访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工 作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因 为越大的元素会经由交换慢慢“浮”到数列的顶端，故名。
算法描述:
- i从0开始，i与i+1比较，如果i>i+1，那么就互换
- i不断增加，直到i<n-1(n是数组元素的个数，n-1是数组已经最后一个元素)，一趟下来，可以让数组元素中最大值排在数组的最后面
从最简单开始，首先我们创建一个数组，该数组有5位数字：
int[] arrays = {2, 5, 1, 3, 4};
- 第一趟排序
下面我们根据算法的描述来进行代码验算(第一趟排序):
//使用临时变量，让两个数互换
int temp;
//第一位和第二位比
if (arrays[0] > arrays[1]) {
//交换
temp = arrays[0];
arrays[0] = arrays[1];
arrays[1] = temp;
}
//第二位和第三位比
if (arrays[1] > arrays[2]) {
temp = arrays[1];
arrays[1] = arrays[2];
arrays[2] = temp;
}
//第三位和第四位比
if (arrays[2] > arrays[3]) {
temp = arrays[2];
arrays[2] = arrays[3];
arrays[3] = temp;
}
//第四位和第五位比
if (arrays[3] > arrays[4]) {
temp = arrays[3];
arrays[3] = arrays[4];
arrays[4] = temp;
}
如果前一位的数比后一位的数要大，那么就交换，直到将数组的所有元素都比较了一遍! 经过我们第一趟比较，我们可以发现:最大的值就在数组的末尾了!
- 第二趟排序
第二趟排序跟第一趟排序一样，也是用前一位与后一位比较，如果前一位比后一位要大，那就交换。值 得注意的是：并不需要与最后一位比较了，因为在第一趟排序完了，最后一位已经是最大的数了。同理，我们第二趟排序完了之后，倒数第二位也是第二大的数了。
第二趟排序的代码如下:
//第一位和第二位比
if (arrays[0] > arrays[1]) {
//交换
temp = arrays[0];
arrays[0] = arrays[1];
arrays[1] = temp;
}
//第二位和第三位比
if (arrays[1] > arrays[2]) {
temp = arrays[1]; arrays[1] = arrays[2]; arrays[2] = temp;
}
//第三位和第四位比
if (arrays[2] > arrays[3]) {
temp = arrays[2]; arrays[2] = arrays[3]; arrays[3] = temp;
}
//第四位不需要和第五位比了，因为在第一趟排序结束后，第五位是最大的了
结果:我们的第二大数已经排在了倒数第二位了
- 代码简化
值得说明的是：上面的结果看起来已经是排序好的了，其实是我在测试时数据还不足够乱，如果数据足够乱的话，是需要4(n-1)趟排序的！
但我们从上面的代码就可以发现:第一趟和第二趟的比较、交换代码都是重复的，并且我们的比较都是
写死的(0,1,2,3,4)，并不通用!
我们的数组有5位数字
第一趟需要比较4次
第二趟需要比较3次
我们可以根据上面规律推断出:
第三趟需要比较2次
第四躺需要比较1次
再从上面的规律可以总结出：**5位数的数组需要4躺排序的，每躺排序之后次数减1(因为前一趟已经把前一趟数的最大值确定下来了)！ **
于是我们可以根据for循环和变量将上面的代码进行简化:
int temp;
//外层循环是排序的趟数
for (int i = 0; i < arrays.length - 1 ; i++) {
//内层循环是当前趟数需要比较的次数
for (int j = 0; j < arrays.length - i - 1; j++) {
//前一位与后一位与前一位比较，如果前一位比后一位要大，那么交换
if (arrays[j] > arrays[j + 1]) {
temp = arrays[j];
arrays[j] = arrays[j + 1];
arrays[j + 1] = temp;
}
}
}
- 冒泡排序优化
从上面的例子我们可以看出来，如果数据足够乱的情况下是需要经过4躺比较才能将数组完整排好序。
但是我们在第二躺比较后就已经得到排好序的数组了。
但是，我们的程序在第二趟排序后仍会执行第三趟、第四趟排序。这是没有必要的，因此我们可以对其 进行优化一下:
如果在某躺排序中没有发生交换位置，那么我们可以认为该数组已经排好序了。 这也不难理解，因为我们每趟排序的目的就是将当前趟最大的数置换到对应的位置上，没有发生置换说明就已经排好序了。
代码如下：
//装载临时变量
int temp;
//记录是否发生了置换， 0 表示没有发生置换、 1 表示发生了置换
int isChange;
//外层循环是排序的趟数
for (int i = 0; i < arrays.length - 1; i++) {
//每比较一趟就重新初始化为0
isChange = 0;
//内层循环是当前趟数需要比较的次数
for (int j = 0; j < arrays.length - i - 1; j++) {
//前一位与后一位与前一位比较，如果前一位比后一位要大，那么交换
if (arrays[j] > arrays[j + 1]) {
temp = arrays[j];
arrays[j] = arrays[j + 1];
arrays[j + 1] = temp;
//如果进到这里面了，说明发生置换了
isChange = 1;
}
}
//如果比较完一趟没有发生置换，那么说明已经排好序了，不需要再执行下去了
if (isChange == 0) {
break;
}
}
2. 选择排序
选择排序介绍和稳定性说明
来源百度百科：
选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元 素中选出最小(或最大)的一个元素，存放在序列的起始(末尾)位置，直到全部待排序的数据元素排 完。选择排序是不稳定的排序方法(比如序列[5， 5， 3]第一次就将第一个[5]与[3]交换，导致第 一个5挪动到第二个5后面)。
上面提到了选择排序是不稳定的排序方法，那我们的冒泡排序是不是稳定的排序方法呢?稳定的意思指的是什么呢?
判断某排序算法是否稳定，我们可以简单理解成：排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同
- 如果相同，则是稳定的排序方法。
- 如果不相同，则是不稳定的排序方法
如果排序前的数组是 [3,3,1] ，假定我们使用选择排序的话，那第一趟排序后结果就是 [1,3,3] 。这 个数组有两个相同的值，它俩在 array[0] 和 array[1] ，结果经过排序， array[0] 的跑到了array[2] 上了。
那么这就导致:2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序不相同，因此，我们就说它是不稳定的
再回到上面的问题，上一篇说讲的冒泡排序是稳定的，主要原因是：俩俩比较的时候，没有对相等的数据进行交换(因为没必要)。因此它不存在2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序不相同。
那么稳定排序的好处是什么?
参考知乎回答@独行侠的回答:
如果我们只对一串数字排序，那么稳定与否确实不重要，因为一串数字的属性是单一的，就是数 字值的大小。但是排序的元素往往不只有一个属性，例如我们对一群人按年龄排序，但是人除了 年龄属性还有身高体重属性，在年龄相同时如果不想破坏原先身高体重的次序，就必须用稳定排 序算法.
很清晰的指出，只有当在“二次”排序时不想破坏原先次序，稳定性才有意义
- 第一趟排序
它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素，存放在序列的起始(末尾)位 置，直到全部待排序的数据元素排完
首先，我们创建数组，找到它最大的值(这就很简单了):
int[] arrays = {2, 3, 1, 4, 3, 5, 1, 6, 1, 2, 3, 7, 2, 3};
//假定max是最大的
int max = 0;
for (int i = 0; i < arrays.length; i++) {
if (arrays[i] > max) {
max = arrays[i]; }
}
效果如下:
随后这个最大的数和数组末尾的数进行交换:
//使用临时变量，让两个数互换 i
nt temp;
temp = arrays[11];
arrays[11] = arrays[13];
arrays[13] = temp;
那么经过第一趟排序，我们的最大值已经到了数组的末尾了。
- 第二趟排序
再次从数组获取最大的数(除了已经排好的那个):
int max2 = 0;
for (int i = 0; i < (arrays.length - 1); i++) {
if (arrays[i] > max2) {
max2 = arrays[i];
}
}
System.out.println(max2);
效果如下:
再将获取到的最大值与数组倒数第二位交换:
temp = arrays[7];
arrays[7] = arrays[12];
arrays[12] = temp;
经过第二次排序，已经能够将数组最大两个数进行排序了
代码简化
从前两趟排序其实我们就可以摸出规律了:
- 一个数组是需要 n-1 趟排序的(因为直到剩下一个元素时，才不需要找最大值)
- 每交换1次，再次找最大值时就将范围缩小1
- 查询当前趟数最大值实际上不用知道最大值是多少(上面我查出最大值，还要我手动数它的⻆标)， 知道它的数组⻆标即可，交换也是根据⻆标来进行交换
第一趟:遍历数组14个数，获取最大值，将最大值放到数组的末尾 [13]
第二趟:遍历数组13个数，获取最大值，将最大值放到数组倒数第二位 [12]
....
数组有14个数，需要13趟排序。
//记录当前趟数的最大值的⻆标
int pos ;
//交换的变量
int temp;
//外层循环控制需要排序的趟数
for (int i = 0; i < arrays.length - 1; i++) {
//新的趟数、将⻆标重新赋值为0
pos = 0;
//内层循环控制遍历数组的个数并得到最大数的⻆标
for (int j = 0; j < arrays.length - i; j++) {
if (arrays[j] > arrays[pos]) {
pos = j;
}
}
//交换
temp = arrays[pos];
arrays[pos] = arrays[arrays.length - 1 - i];
arrays[arrays.length - 1 - i] = temp;
}
System.out.println("Arrays" + arrays);
3. 插入排序
插入排序介绍
来源百度百科:
插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数 加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。
将一个数据插入到已经排好序的有序数据中
将要排序的是一个乱的数组 int[] arrays = {3, 2, 1, 3, 3}; 在未知道数组元素的情况下，我们只能把数组的第一个元素作为已经排好序的有序数据，也就是说，把 {3} 看成是已经排好序的有序数据
- 第一趟排序
用数组的第二个数与第一个数(看成是已有序的数据)比较
- 如果比第一个数大，那就不管他
- 如果比第一个数小，将第一个数往后退一步，将第二个数插入第一个数去
int temp;
if (arrays[1] > arrays[0]) {
//如果第二个数比第一个数大，直接跟上
} else { //如果第二个数比第一个数小，将第一个数后退一个位置(将第二个数插进去) temp = arrays[1];
arrays[1] = arrays[0];
arrays[0] = temp;
}
System.out.println("公众号Java3y" + arrays);
效果如下:
- 第二趟排序
用数组的第三个数与已是有序的数据 {2,3} (刚才在第一趟排的)比较
- 如果比第二位的数大，那就不管它
- 如果比第二位的数小，那就将第二的位置退一个位置，让第三个数和第一位比较
如果第三个数比第一位大，那么将第三个数插入到第二的位置上 如果第三个数比第一位小，那么将第一位后退一步，将第三个数插入到第一的位置上
//第二趟排序--------------------
if (arrays[2] > arrays[1]) {
//如果第三个数比第二个数大，直接跟上
} else {
//如果第三个数比第二个数小，将第二个数往后退一个位置，让第三个数跟第一个数比
temp = arrays[2];
arrays[2] = arrays[1];
//如果第三个数比第一个大，那就插入到第二个数中
if (temp > arrays[0]) {
arrays[1] = temp; } else {
//如果第三个数比第一个小，将第三个数插入到第一个数前面 int swapTemp = arrays[0];
arrays[0] = temp;
arrays[1] = swapTemp;
}
}
System.out.println("公众号Java3y" + arrays);
效果如下:
简化代码
从前两趟排序我们可以摸出的规律:
- 首先将已排序的数据看成一个整体
- 一个数组是需要 n-1 趟排序的，总是用后一位跟 已排序的数据比较(第一趟:第二位跟 已排序的数 据 比，第二趟:第三位跟 已排序的数据比)
- 用第三位和 已排序的数据 比，实际上就是让第三位数跟两个数比较，只不过这两个数是已经排好序 的而已。而正是因为它排好序的，我们可以使用一个循环就可以将我们比较的数据插入进去
for (int i = 1; i < arrays.length; i++) {
temp = arrays[i];
//如果前一位(已排序的数据)比当前数据要大，那么就进入循环比较[参考第二趟排序] int j = i - 1;
while (j >= 0 && arrays[j] > temp) {
//往后退一个位置，让当前数据与之前前位进行比较
arrays[j + 1] = arrays[j];
//不断往前，直到退出循环
j--;
}
//退出了循环说明找到了合适的位置了，将当前数据插入合适的位置中
arrays[j + 1] = temp;
}
System.out.println("公众号Java3y" + arrays);
4. 快速排序
快速排序的介绍
来源百度百科:
快速排序由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成 独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这 两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
快速排序是面试出现的可能性比较高的，也是经常会用到的一种排序，应该重点掌握。 前面一个章节已经讲了递归了，那么现在来看快速排序就非常简单了.
- 第一趟快速排序
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小
百度百科的话并没有说到重点，更简单的理解是这样的：在数组中找一个支点(任意),经过一趟排序后， 支点左边的数都要比支点小，支点右边的数都要比支点大!
现在我们有一个数组: int arr[]={1,4,5,67,2,7,8,6,9,44};
经过一趟排序之后，如果我选择数组中间的数作为支点:7(任意的)，那么第一趟排序后的结果是这样的: {1,4,5,6,2,7,8,67,9,44}
那么就实现了支点左边的数比支点小，支点右边的数比支点大
- 递归分析与代码实现
现在我们的数组是这样的: {1,4,5,6,2,7,8,67,9,44} ，既然我们比7小的在左边，比7大的在右边， 那么我们只要将”左边“的排好顺序，又将”右边“的排好序，那整个数组是不是就有序了?想一想，是不是?
又回顾一下递归:”左边“的排好顺序，”右边“的排好序，跟我们第一趟排序的做法是不是一致的?
只不过是参数不一样：第一趟排序是任选了一个支点，比支点小的在左边，比支点大的在右边。那么，我们想要”左边“的排好顺序，只要在”左边“部分找一个支点，比支点小的在左边，比支点大的在右边
..............
在数组中使用递归依照我的惯性，往往定义两个变量: L 和 R ， L 指向第一个数组元素， R 指向在最后 一个数组元素
递归出口也很容易找到：如果数组只有一个元素时，那么就不用排序了所以，我们可以写出这样的代码:
public static void main(String[] args) {
int[] arr = {1, 4, 5, 67, 2, 7, 8, 6, 9, 44};
quickSort(arr, 0, 9);
System.out.println("arr" + arr);
}
/**
* 快速排序
*
* @param arr
* @param L 指向数组第一个元素
* @param R 指向数组最后一个元素
*/
public static void quickSort(int[] arr, int L, int R) {
int i = L;
int j = R;
//支点
int pivot = arr[(L + R) / 2];
//左右两端进行扫描，只要两端还没有交替，就一直扫描
while (i <= j) {
//寻找直到比支点大的数
while (pivot > arr[i])
i++;
//寻找直到比支点小的数
while (pivot < arr[j])
j--;
//此时已经分别找到了比支点小的数(右边)、比支点大的数(左边)，它们进行交换
if (i <= j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}
//上面一个while保证了第一趟排序支点的左边比支点小，支点的右边比支点大了。
//“左边”再做排序，直到左边剩下一个数(递归出口)
if (L < j)
quickSort(arr, L, j);
//“右边”再做排序，直到右边剩下一个数(递归出口)
if (i < R)
quickSort(arr, i, R);
}
效果如下:
5. 归并排序
来源百度百科:
归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法 (Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序 列;即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二 路归并。
过程描述:
归并过程为:比较a[i]和b[j]的大小，若a[i]≤b[j]，则将第一个有序表中的元素a[i]复制到r[k]中，并 令i和k分别加上1;否则将第二个有序表中的元素b[j]复制到r[k]中，并令j和k分别加上1，如此循 环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复制到r中从下标k到下 标t的单元。归并排序的算法我们通常用递归实现，先把待排序区间[s,t]以中点二分，接着把左边 子区间排序，再把右边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间 [s,t]。
原理:
归并操作的工作原理如下:
- 第一步:申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
- 第二步:设定两个指针，最初位置分别为两个已经排序序列的起始位置
- 第三步:比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
- 重复步骤3直到某一指针超出序列尾
- 将另一序列剩下的所有元素直接复制到合并序列尾
下面我就来做个小小的总结:
将两个已排好序的数组合并成一个有序的数组,称之为归并排序
步骤：遍历两个数组，比较它们的值。谁比较小，谁先放入大数组中，直到数组遍历完成
- 演算归并排序过程
现在我有两个已经排好顺序的数组: int[] arr1 = {2, 7, 8} 和 int[] arr2 = {1, 4, 9} ，我还 有一个大数组来装载它们 int[] arr = new int[6];
1.1 第一步
那么，我将两个数组的值进行比较，谁的值比较小，谁就放入大数组中!
首先，拿出 arr1[0] 和 arr2[0] 进行比较，显然是 arr2[0] 比较小，因此将 arr2[0] 放入大数组中， 同时 arr2 指针往后一格
所以，现在目前为止 arr = {1}
1.2 第二步
随后，拿 arr1[0] 和 arr2[1] 进行比较，显然是 arr1[0] 比较小，将 arr1[0] 放入大数组中，同时 arr1 指针往后一格
所以，现在目前为止 arr = {1,2}
1.3 第三步
随后，拿 arr1[1] 和 arr2[1] 进行比较，显然是 arr2[1] 比较小，将 arr2[1] 放入大数组中，同时 arr2 指针往后一格
所以，现在目前为止 arr = {1,2,4}
........
遍历到最后，我们会将两个已排好序的数组变成一个已排好序的数组 arr = {1,2,4,7,8,9}
- 归并排序前提分析(分治法)
从上面的演算我们就直到，归并排序的前提是需要两个已经排好顺序的数组，那往往不会有两个已经排
好顺序的数组给我们的呀(一般是杂乱无章的一个数组)，那这个算法是不是很鸡肋的呢??
其实并不是的，首先假设题目给出的数组是这样子的: int[] arr = {2, 7, 8, 1, 4, 9};
当我们要做归并的时候就以 arr[3] 也就元素为1的那个地方分开。是然后用一个 指针L 指向 arr[0] ， 一个 指针M 指向 arr[3] ，用一个 指针R 指向 arr[5] (数组最后一位)。有了指针的帮助，我们就可以将 这个数组切割成是两个有序的数组了(操作的方式就可以和上面一样了)
可是上面说了，一般给出的是杂乱无章的一个数组，现在还是达不到要求。比如给出的是这样一个数 组: int[] arrays = {9, 2, 5, 1, 3, 2, 9, 5, 2, 1, 8};
此时，我们就得用到分治的思想了:
那么我们也可以这样想将 int[] arr = {2, 7, 8, 1, 4, 9}; 数组分隔成一份一份
的， arr[0] 它是一个有序的"数组", arr[1] 它也是一个有序的"数组",利用指针(L,M,R)又可以像操 作两个数组一样进行排序。最终合成 {2,7} .......再不断拆分合并，最后又回到了我们的 arr = {1,2,4,7,8,9} ，因此归并排序是可以排序杂乱无章的数组的
这就是我们的分治法--->将一个大问题分成很多个小问题进行解决，最后重新组合起来
- 归并代码实现
实现步骤: - 拆分
- 合并 ........
public static void main(String[] args) {
int[] arrays = {9, 2, 5, 1, 3, 2, 9, 5, 2, 1, 8}; mergeSort(arrays, 0, arrays.length - 1);
System.out.println("公众号:Java3y" + arrays); }
/**
* 归并排序
*
* @param arrays
* @param L
* @param R */
指向数组第一个元素 指向数组最后一个元素
public static void mergeSort(int[] arrays, int L, int R) {
//如果只有一个元素，那就不用排序了
if (L == R) {
return;
} else {
//取中间的数，进行拆分
int M = (L + R) / 2;
//左边的数不断进行拆分
mergeSort(arrays, L, M);
//右边的数不断进行拆分
mergeSort(arrays, M + 1, R);
//合并
merge(arrays, L, M + 1, R);
}
}
/**
* 合并数组
*
* @param arrays
* @param L
* @param M
* @param R */
指向数组第一个元素 指向数组分隔的元素 指向数组最后的元素
public static void merge(int[] arrays, int L, int M, int R) { //左边的数组的大小
int[] leftArray = new int[M - L];
//右边的数组大小
int[] rightArray = new int[R - M + 1];
//往这两个数组填充数据
for (int i = L; i < M; i++) {
leftArray[i - L] = arrays[i]; }
for (int i = M; i <= R; i++) { rightArray[i - M] = arrays[i];
}
int i = 0, j = 0;
// arrays数组的第一个元素
int k=L;
//比较这两个数组的值，哪个小，就往数组上放
while (i < leftArray.length && j < rightArray.length) {
//谁比较小，谁将元素放入大数组中,移动指针，继续比较下一个 if (leftArray[i] < rightArray[j]) {
arrays[k] = leftArray[i];
i++;
k++;
} else {
arrays[k] = rightArray[j]; j++;
k++;
}
}
//如果左边的数组还没比较完，右边的数都已经完了，那么将左边的数抄到大数组中(剩下的都 是大数字)
while (i < leftArray.length) { arrays[k] = leftArray[i]; i++;
k++;
}
//如果右边的数组还没比较完，左边的数都已经完了，那么将右边的数抄到大数组中(剩下的都 是大数字)
while (j < rightArray.length) {
arrays[k] = rightArray[j];
k++;
j++;
}
}
6. 希尔排序介绍
来源百度百科:
希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”(Diminishing Increment Sort)， 是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因D.L.Shell 于1959年提出而得名。
从上面我们很容易看出来，它是插入排序的高级版
从直观上看希尔排序:
就是把数列进行分组(不停使用插入排序)，直至从宏观上看起来有序，最后插入排序起来就容易了 (无须多次移位或交换)。*
那么，上面那里说了将一个序列分成好几个序列，那么到底怎么分呢?比如有10个元素的序列，分成几 个才合适?每次缩减又是多少呢?
从专业的⻆度上讲，将一个序列分成好几个序列，用一个数来表示:那个数称为增量。显然的是，增量 是不断递减的(直到增量为1)
往往的:如果一个数列有10个元素，我们第一趟的增量是5，第二趟的增量是2，第三趟的增量是1。如 果一个数列有18个元素，我们第一趟的增量是9，第二趟的增量是4，第三趟的增量是2，第四趟的增量 是1
很明显我们可以用一个序列来表示增量: {n/2,(n/2)/2...1} ，每次增量都 /2
- 希尔排序体验
现在我们有一个数组，该数组有6个元素
int[] arrays = {2, 5, 1, 3, 4, 6};
排序前:
- 将该数组看成三个(arrays.length/2)数组，分别是: {2,3} , {5,4} , {1,6}
第一趟排序: - 对三个数组分别进行插入排序，因此我们三个数组得到的结果为 {2,3} , {4,5} , {1,6} 此时数组是这样子的: {2, 4, 1, 3, 5, 6}
第二趟排序:
增量减少了，上面增量是3，此时增量应该为1了，因此把 {2, 4, 1, 3, 5, 6} 看成一个数组(从宏观上是有序的了)，对其进行插入排序，直至有序
7. 堆排序
- 堆排序介绍
来源百度百科:
堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法，它是选择排序的 一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。
前面我已经有二叉树入⻔的文章了，当时讲解的是二叉查找树，那上面所说的完全二叉树是怎么样的一 种二叉树呢??还有满二叉树又是怎么的一种二叉树呢??甚至还有完满二叉树??
-
完全二叉树: 除了最后一层之外的其他每一层都被完全填充，并且所有结点都保持 -向左对⻬。
image.png -
满二叉树:除了叶子
结点之外的每一个结点都有两个孩子，每一层(当然包含最后一层)都被完全填充。
image.png -
完满二叉树:除了叶子结点之外的每一个结点都有两个孩子结点。
image.png
简单来说:堆排序是将数据看成是完全二叉树、根据完全二叉树的特性来进行排序的一种算法
- 最大堆要求节点的元素都要不小于其孩子，最小堆要求节点元素都不大于其左右孩子
- 那么处于最大堆的根节点的元素一定是这个堆中的最大值
这里我们讨论最大堆:当前每个父节点都大于子节点
完全二叉树有个特性: 左边子节点位置 = 当前父节点的两倍 + 1 ， 右边子节点位置 = 当前父节点的两倍 +2
-
堆排序体验
现在我们有一个完全二叉树:左子树和右子树都符合最大堆--> 父>子
image.png
但是我们会发现:根元素所在的数并不符合，明显的是:1是小于7的
我们就对其进行交换，交换完之后我们会发现:右子树又不符合了~
因为，右子树变成了这样:
最后，我们将右子数的最大值也交换到右子树的根元素上
于是我们第一次的建堆操作就完成了!
可以发现的是:一次堆建立完之后，我们的最大值就在了堆的根节点上 随后将堆顶最大值和数组最后的元素进行替换，我们就完成了一趟排序了。
接下来，剩下的数不断进行建堆，交换就可以完成我们的堆排序了
.........建堆，交换....建堆，交换...建堆，交换...建堆，交换..
- 堆排序代码实现
比较当前父节点是否大于子节点，如果大于就交换，直到一趟建堆完成~
/**
* 建堆 *
* @param arrays 看作是完全二叉树
* @param currentRootNode 当前父节点位置
* @param size 节点总数 */
public static void heapify(int[] arrays, int currentRootNode, int size) {
if (currentRootNode < size) {
//左子树和右字数的位置
int left = 2 * currentRootNode + 1;
int right = 2 * currentRootNode + 2;
//把当前父节点位置看成是最大的
int max = currentRootNode;
if (left < size) { //如果比当前根元素要大，记录它的位置
if (arrays[max] < arrays[left]) {
max = left;
}
}
if (right < size) {
//如果比当前根元素要大，记录它的位置
if (arrays[max] < arrays[right]) {
max = right; }
}
//如果最大的不是根元素位置，那么就交换
if (max != currentRootNode) {
int temp = arrays[max];
arrays[max] = arrays[currentRootNode];
arrays[currentRootNode] = temp;
//继续比较，直到完成一次建堆
heapify(arrays, max, size);
}
} }
值得注意的是:在上面体验堆排序时，我们是左子树和右子数都是已经有 父>子 这么一个条件的了。
- 显然，一个普通的数组并不能有这种条件(父>子)，因此，我们往往是从数组最后一个元素来进行 建堆
/**
* 完成一次建堆，最大值在堆的顶部(根节点) */
public static void maxHeapify(int[] arrays, int size) {
// 从数组的尾部开始，直到第一个元素(⻆标为0)
for (int i = size - 1; i >= 0; i--) {
heapify(arrays, i, size);
}
}
完成第一次建堆之后，其它下边的分叶子节点都在自己该在的位置了，我们会发现最大值会在数组的首位:
public static void main(String[] args) {
int[] arrays = {6, 3, 8, 5,2,-1,-5,-2,-6,345,7, 5, 1, 2, 23, 4321,432,3,2,34234,2134,1234, 5, 132423, 234, 4, 2, 4, 1, 5, 2, 5};
// 完成一次建堆..
maxHeapify(arrays, arrays.length - 1);
int size = arrays.length - 1;
for (int i = 0; i < arrays.length; i++) {
//交换
int temp = arrays[0];
arrays[0] = arrays[(arrays.length - 1) - i];
arrays[(arrays.length - 1) - i] = temp;
// 调整位置 heapify(arrays, 0, size);
size--;
}
System.out.println("Arrays：" + arrays); }
/**
* 完成一次建堆，最大值在堆的顶部(根节点)
*/
public static void maxHeapify(int[] arrays, int size) { for (int i = size - 1; i >= 0; i--) {
heapify(arrays, i, size);
}
}
/**
* 建堆 *
* @param arrays
* @param currentRootNode 当前父节点位置
* @param size 节点总数 */
public static void heapify(int[] arrays, int currentRootNode, int size) {
if (currentRootNode < size) { //左子树和右字数的位置
int left = 2 * currentRootNode + 1; int right = 2 * currentRootNode + 2;
//把当前父节点位置看成是最大的 int max = currentRootNode;
if (left < size) { //如果比当前根元素要大，记录它的位置
if (arrays[max] < arrays[left]) {
max = left; }
}
if (right < size) {
//如果比当前根元素要大，记录它的位置
if (arrays[max] < arrays[right]) {
max = right; }
}
//如果最大的不是根元素位置，那么就交换 if (max != currentRootNode) {
int temp = arrays[max];
arrays[max] = arrays[currentRootNode]; arrays[currentRootNode] = temp;
//继续比较，直到完成一次建堆
heapify(arrays, max, size);
}
}
}
效果如下:
8. 基数排序(桶排序)
数排序不同与其他的7种排序，其他7种排序本 质上都是按照交换或者比较来进行排序，但是基数排序并不是，它是按照分配，回收(分配到不同的位置 上，然后回收)..不断分配..回收来进行排序，直到有序..
过程
- 第一趟桶排序将数字的个位数分配到桶子里面去，然后回收起来，此时数组元素的所有个位数都已 经排好顺序了
- 第二趟桶排序将数字的十位数分别分配到桶子里面去，然后回收起来，此时数组元素的所有个位数 和十位数都已经排好顺序了(如果没有十位数、则补0)
- 第三趟桶排序将数字的百位数分别分配到桶子里面去，然后回收起来，此时数组元素的所有个位数 和十位数和百位数都已经排好顺序了(如果没有百位数、则补0)
- ..................................
- 直至全部数(个、十、百、千位...)排好顺序，那么这个数组就是有序的了。
关于这个桶我们可以用二维数组来进行存放。 10个桶子就是10列，如果分配时有的数字相同的话，那么就弄成多行~
-
基数排序体验
首先我们有以下这个数组:
int[] arrays = {6, 4322, 432, 344, 55 };
现在我们有10个桶子，每个桶子下能装载 arrays.length 个数字..
int[][] buckets = new int[arrays.length][10];
效果如下:
image.png
2.1 第一趟分配与回收
将数组的每个个位数进行分配到不同的桶子上:
分配完之后，我们按照顺序来进行回收:得到的结果应该是这样子的: {4322,432,344,55,6}
2.2 第二趟分配与回收
将数组的每个十位数进行分配到不同的桶子上(像6这样的数，往前边补0):
于是我们可以得到这样的排序:
2.3 第三趟分配与回收
将数组的每个百位数进行分配到不同的桶子上(像6、55这样的数，往前边补0):
于是我们可以得到这样的排序:
分配完之后，我们按照顺序来进行回收:得到的结果应该是这样子的: {6,55,4322,344,432}
2.4 第四趟分配与回收
将数组的每个百位数进行分配到不同的桶子上(像6、55，344，432这样的数，往前边补0):
于是我们可以得到这样的排序:
分配完之后，我们按照顺序来进行回收:得到的结果应该是这样子的: {6,55,344,432,4322}
此时我们的数组就已经可以排好序了~~~过程就是这样子，其实不难就只有两个步骤:
- 将数组的每一位放进桶子里
- 回收
- 循环......
- 基数排序代码编写
我们的基数排序是按照个、十、百、千位...来进行存放的。前面的演示是已经知道数组元素的数据的情 况下来进行存放，但是一般我们是不去理会数组内元素的值的。那如果位数很多(万位)或者都是个位 数，这个条件我们怎么去处理呢?
我们可以这样做:先求出数组最大的值，然后不断/10，只要它能大于0，那么它的位数还有~:
3.1 求出数组最大的值
这个我在前面写递归的时候就有这个代码了，我就直接搬去递归的代码过来了，顺便复习一哈吧:
当然了，更好的是直接用for循环来找出来就行了(易读性好一些)
/**
* 递归，找出数组最大的值
* @param arrays 数组
* @param L 左边界，第一个数
* @param R 右边界，数组的⻓度 * @return
*/
public static int findMax(int[] arrays, int L, int R) {
//如果该数组只有一个数，那么最大的就是该数组第一个值了 if (L == R) {
return arrays[L];
} else {
int a = arrays[L];
int b = findMax(arrays, L + 1, R);//找出整体的最大值
if (a > b) {
return a;
} else {
return b;
} }
3.2 代码实现
public static void radixSort(int[] arrays) {
int max = findMax(arrays, 0, arrays.length - 1);
//需要遍历的次数由数组最大值的位数来决定
for (int i = 1; max / i > 0; i = i * 10) {
int[][] buckets = new int[arrays.length][10];
//获取每一位数字(个、十、百、千位...分配到桶子里)
for (int j = 0; j < arrays.length; j++) {
int num = (arrays[j] / i) % 10;
//将其放入桶子里
buckets[j][num] = arrays[j];
}
//回收桶子里的元素
int k = 0;
//有10个桶子
for (int j = 0; j < 10; j++) {
//对每个桶子里的元素进行回收
for (int l = 0; l < arrays.length ; l++) {
//如果桶子里面有元素就回收(数据初始化会为0)
if (buckets[l][j] != 0) {
arrays[k++] = buckets[l][j];
}
}
}
}
}
搞了一堆数测试了一哈:
桶排序(基数排序)总结
基数排序(桶排序)要理解起来并不困难，不过值得注意的是:基数排序对有负数和0的数列难以进行排序
- 因此，往往有0和负数的数组一般我们都不用基数来进行排序
基数排序的要点就两个: - 分配:按照元素的大小来放入不同的桶子里
- 回收:将桶子里的元素按桶子顺序重新放到数组中
- 重复.....两个步骤
