- 前言
- ❤️冒泡排序
- 🤍演示说明
- 🤍优化
- 🤍分析
- ❤️选择排序
- 🤍演示说明
- 🤍分析
- ❤️插入排序
- 🤍演示说明
- 🤍分析
- ❤️希尔排序
- 🤍演示说明
- 🤍分析
- ❤️快速排序
- 🤍演示说明
- 🤍分析
- ❤️归并排序
- 🤍演示说明
- 🤍分析
- ❤️计数排序
- 🤍演示说明
- 🤍分析
- ❤️基数排序
- 🤍演示说明
- 🤍分析
- ❤️桶排序
- 🤍演示说明
- 🤍分析
- ❤️堆排序
- 🤍演示说明
- 🤍分析
- 💯总结
前言
算法是程序设计的灵魂，我们最先接触的算法就是排序算法了，尤其是冒泡排序估计大家闭着眼都能写出来，对于其它的排序算法你还了解哪些？本文就带大家回顾一下算法界的十大排序算法。本次排序算法主要讲解算法的简单实现、时间复杂度和稳定性(稳定性指的是相同数据排序前后的顺序不变)。
推荐演示的时候使用网站https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html，网站随机数组有点长，我没找到自定义数组的功能，所以一部分动图采用别的网站制作的，没有的采用这个网站制作的。
❤️冒泡排序 🤍演示说明
冒泡排序是最常见的排序算法了，它是通过从前往后依次对比排序序列中相邻的两个值来进行的，对比的时候如果两个值的大小与排序的目的相反，则将他们交换过来。
🔊 看一下动画演示效果：
🔊 下面看一下代码实现
public static int[] sort(int[] array) {
//正常是比较length遍的，但是最后还剩一个的那次不算了所以是length-1遍
for (int i = 0; i < array.length - 1; i++) {
//遍历数组，对数组中相邻的两个数据进行比较并交换
for (int j = 0; j < array.length - 1 - i; j++) {
if (array[j] > array[j + 1]) {
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
return array;
}
正常情况下很少有将代码执行完全了之后才排序完成的，大多数情况下在执行过程中就完成了排序，所以完成了排序之后继续执行代码完全是浪费计算机了，是不是可以确定排序执行完成之后就不再执行了呢？
🔊 怎么确定排序完成了呢？咱可以在循环的时候加一个标志位，如果本轮替换循环结束都没有发生排序，那就说明此时已经排序完成了直接跳出循环就可以了。看一下代码实现：
public static int[] sort(int[] array) {
//正常是比较length遍的，但是最后还剩一个的那次不算了所以是length-1遍
for (int i = 0; i < array.length - 1; i++) {
//遍历数组，对数组中相邻的两个数据进行比较并交换
boolean flag = true;
for (int j = 0; j < array.length - 1 - i; j++) {
/*或运算，如果有true则为true*/
if (array[j] > array[j + 1]) {
flag = false;
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
//如果标志位没有被修改说明本次执行没有需要替换的值
if(flag){
break;
}
}
return array;
}
当然冒泡排序的优化很多优化后的性能非常好的方案(像双向排序等)，咱本文就简单的介绍一下，主要作为初级入门的只是讲解。
🤍分析空间复杂度咱就不分析了，一般情况不会出现因为空间复杂度原因导致内存溢出异常的。
🔊 时间复杂度
最好的情况： 如果当前需要排序的数组中的内容已经是排好序的，这时候for循环只需要执行一遍就可以了，此时的时间复杂度是O(n)。
最坏的情况： 如果当前需要排序的数组是倒序的，那么整个执行代码需要完整的走下来才能排序完成，最终走了两层for循环，此时的时间复杂度为O(n2)。
🔊 稳定性
冒泡排序中两两交换的时候使用的是大于或小于才交换的，没有等于交换，所以排序前后相同元素顺序没有改变，是稳定的。
选择排序也是一种常见的排序算法，它的思路是从一串数组中找出最大或最小的数据替换到对应的位置，例如如果按照升序排列每次循环找到最小的数据从左往右替换，直到最后数组变成有序的了。
🔊直接看一下演示效果：
🔊 下面看一下代码实现
public static int[] sort(int[] array) {
for (int i = 0; i < array.length - 1; i++) {
//一个临时变量每次循环记录最小值的下标位置
int min = i;
for (int j = i + 1; j < array.length; j++) {
//如果有比这个值小的就替换下标位置
if(array[j] < array[min]) {
min = j;
}
}
//数据交换,为了代码可读性放在了一个大括号里分割了下
{
int temp = array[i];
array[i] = array[min];
array[min] = temp;
}
}
return array;
}
选择排序可能也存在中间过程执行的时候出现排序已经完成的情况，但是我们无法判断是否排序完成，除非再加上冒泡排序的比较结合，那还不如直接使用冒泡呢。
🔊 时间复杂度
所以选择排序的时间复杂度没有最好和最坏情况的区分，所有情况都需要执行结束它的时间复杂度为两层for循环O(n2)。
🔊 稳定性
选择排序在排序过程中涉及到交换，而且交换不固定，可能相同元素被另一个元素替换走了，所以是不稳定的。
插入排序是把整个待排序的数组看成一个有序的数组和一个无序的数组两个数组，一开始第一个默认有序的，后面的所有的默认无序，把无序中的第一个取出放在有序数组顺序合适的位置。以此类推，看一下分析演示图：
🔊 下面看一下代码实现
public static int[] sort(int[] array) {
for (int i = 1; i < array.length; i++) {
int value = array[i]; //这是无序数组的第一个值
int j; //这是这个值要插入有序数组的位置
//开始遍历有序数组,找这个值要插入的位置j
//j>=0防止数组越界
//因为是有序数组，所以temp第一次大于某个值时，那么temp的下标就是那里了
for (j = i - 1; j >= 0 && value < array[j]; j--) {
//从有序数组的后面往前找，因为要插入所以数组需要后移,所以是倒序循环有序部分
System.out.println("value="+value+";temp="+array[j]);
array[j+1] = array[j];
}
//将数据插入到对应位置
array[j+1] = value;
}
return array;
}
插入排序可能稍微难一点，有点绕所以多加了行打印语句来分析，简单的来分析一点，后面的可以参照动画图自己分析，第一次执行value为5,5直接大于3了，所以没有进入循环，当前下标就是它的下标；第二次进入value=2，temp为5，2<5，5往后移，继续2与3比较，2<3，所以3往后移，循环结束，2放在0的位置。。。
插入排序也分为最好的结果和最坏的结果两种情况
🔊 时间复杂度
最好的结果： 最好的结果就是数据原来就是所需要的顺序，所以排序过程中中间的for循环进不去，最终时间复杂度为O(n)。
最坏的结果： 最坏的结果就是数据跟所需要的顺序相反，排序过程中中间的for循环每次都进行完整走一遍，最终时间复杂度为O(n2）。
🔊 稳定性
插入排序从无序数组插入的有序数组的过程中用的单纯大于小于比较，没有等于，所以相同元素的顺序没有发生改变，是稳定的。
希尔排序是把序列按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量的逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个序列恰好被分为一组，算法便终止。
简单的来说希尔排序是把数据分为间隔的几组，分别对几组进行排序，然后缩小间隔继续排序，直到间隔为1的时候排序完成。希尔排序是对插入排序最差情况的优化，假设插入排序应该在前面的数据在数组中排在后面，排序的时间复杂度O(n2)性能太低，所以我们对其优化。
演示效果图，上面使用的网站没有希尔排序的演示设置，使用了另一个网站，数据有点多没找到自定义设置，所以时间有点长。
根据动图的演示效果可以看出来希尔排序是先把数组进行再次分组排序，尽量把数组放在对应的位置错位不是太大，最后一次进行插入排序的时候不需要移动这么多次。
🔊 下面看一下代码实现
public static int[] sort(int[] array) {
//增量
int gap = array.length / 2;
//如果增量为0则退出
while (gap > 0) {
//这还是那个插入排序，只不过每次的步进使用的gap增量
for (int i = gap; i < array.length; i++) {
int value = array[i];
int j;
//同样的使用的插入排序,j修改为了gap递进的
for (j = i - gap; j >= 0 && value < array[j]; j = j - gap) {
array[j + gap] = array[j];
}
//插入
array[j + gap] = value;
}
//增量每次减少，一般设置为/2，虽然--也没问题，但是考虑综合效率/2更好
gap = gap / 2;
}
return array;
}
希尔排序主要是为插入排序做了些准备工作，将插入排序的时间复杂度往中间集结了一下。
🔊 时间复杂度
希尔排序的时间复杂度与增量有关，Hibbard提出了增量序列{1,3,7，…,2k-1}(质数增量)，这种序列的时间复杂度(最坏情形)为O(n1.5)，而我们使用的2倍增量的时间复杂度最坏的情况下是O(n2)。
🔊 稳定性
希尔排序中涉及到了分组，而且分组是间隔分组，可能拆分两个相同元素的顺序，所以是不稳定的。
快速排序是通过一趟排序将想要排序的数组分割成两个独立的部分，其中一部分的所有数据比另一部分的所有数据要小，然后再按照快速排序递归继续处理，到最后整个数据都变成了有序数组了。每次排序都使用的冒泡排序，所以快速排序是对冒泡排序的优化。看一下实现思路：
演示图采用的单边循环法，来解释下演示图是什么思路：
选取第一个数据18为基准数，比18大的往右移动，比18小的往左移动。最后会以18位界限将数组分成两部分，左边比18小，右边比18大；然后分别对左右两边两个逻辑数组继续重复这样的 *** 作，以此类推，直到最后整个数据的顺序排列完成。
🔊 下面看一下代码实现
public static int[] sort(int[] array, int startIndex, int endIndex) {
//结束条件，开始在索引大于结束索引
if (startIndex >= endIndex) {
return array;
}
// 基准元素位置
int pivotIndex = partition(array, startIndex, endIndex);
//将数组以基准元素分为左右两部分，继续执行
sort(array, startIndex, pivotIndex - 1);
sort(array, pivotIndex + 1, endIndex);
return array;
}
/*分治 单边循环法*/
private static int partition(int[] array, int startIndex, int endIndex) {
//选取第一个元素为基准数据
int pivot = array[startIndex];
//基准数据的下标
int mark = startIndex;
for (int i = startIndex + 1; i <= endIndex; i++) {
//如果值比基准数据小往左边放,基准坐标往右移动
if (array[i] < pivot) {
mark++;
int p = array[mark];
array[mark] = array[i];
array[i] = p;
}
}
array[startIndex] = array[mark];
array[mark] = pivot;
return mark;
}
/*分治 双边循环法*/
private static int partition(int[] array, int startIndex, int endIndex) {
//选取第一个元素为基准数据
int pivot = array[startIndex];
//基准数据的下标
int left = startIndex;
int right = endIndex;
while (left != right) {
//控制right左移比较
while (left < right && array[right] > pivot) {
right--;
}
//控制left右移比较
while (left < right && array[left] <= pivot) {
left++;
}
//交换left和right 指针所指向的元素
if (left < right) {
int p = array[left];
array[left] = array[right];
array[right] = p;
}
}
array[startIndex] = array[left];
array[left] = pivot;
return left;
}
🔊 时间复杂度
快速排序有单边排序和双边排序，演示图是演示的单边排序，双边排序是从左右两头对基准值进行比较，比单边排序更快一点。
快速排序的时间复杂度是O(n*logn)，但是如果选取的基准值是整个数组中的极值时，时间复杂度会退化为O(n2)。
🔊 稳定性
快速排序分割了拆分了数组，有可能使相同元素的顺序改变是不稳定的。
归并排序也是一个采用分治算法的经典排序实现，它是将数组拆分成多个小的数组进行排序，然后再将小的数组逐渐合并排序，到最后实现数组的完全排序。
思路很简单，看一下演示图：将数组每两个分一组进行排序，然后两两合并四个一组排序，然后再合并8个一组排序。。。直到最后完成排序。
🔊 下面看一下代码实现
public static int[] sort(int[] array, int startIndex, int endIndex) {
//结束条件
if (startIndex >= endIndex) {
return array;
}
//折半
int midIndex = (startIndex + endIndex) / 2;
sort(array, startIndex, midIndex);
sort(array, midIndex + 1, endIndex);
//数组两两合并
return merge(array, startIndex, midIndex, endIndex);
}
private static int[] merge(int[] array, int startIndex, int midIndex, int endIndex) {
int[] tempArray = new int[endIndex-startIndex+1];
int index1 = startIndex;
int index2 = midIndex + 1;
int index = 0;
//对两个数组进行比较排序，并放入新的数组中
while (index1 <= midIndex && index2 <= endIndex) {
if (array[index1] <= array[index2]) {
tempArray[index++] = array[index1++];
} else {
tempArray[index++] = array[index2++];
}
}
//将右边剩余元素填充到数组中
while (index1 <= midIndex) {
tempArray[index++] = array[index1++];
}
//将左边剩余元素填充到数组中
while (index2 <= endIndex) {
tempArray[index++] = array[index2++];
}
//重新调整数组
for (int i = 0; i < tempArray.length; i++) {
array[i + startIndex] = tempArray[i];
}
return array;
}
🔊 时间复杂度
归并排序法与快速排序法相类似，都是采用了分治算法，所以其时间复杂度为O(n*logn)；
🔊 稳定性
归并排序拆分数组之前就是按照原始数组的顺序拆分的，再排序过程中相同元素的顺序没有改变，所以是稳定的。
计数排序不是比较排序，而是基于一定长度的数组下标实现的排序算法，因为数据的下标是整数，对整数排序的时候可以将对应的值放在数组下标对应的位置，是一个比较简单的排序算法。
直接看下面的演示图，原理还是比较简单的，将数据放在数组对应下标为1，如果存在就继续++。
🔊 下面看一下代码实现
public static int[] sort(int[] array) {
//先获取数组的最大值
int max = array[0];
for (int i = 0; i < array.length; i++) {
if (array[i] > max) {
max = array[i];
}
}
//数组是从0开始的
int[] currentArray = new int[max+1];
//存放在中间下标数组中
for (int i = 0; i < array.length; i++) {
currentArray[array[i]]++;
}
int[] resultArray = new int[array.length];
//对中间数组遍历放在新数组里面
for (int i = 0, k = 0; i < currentArray.length; i++) {
for (int j = 0; j < currentArray[i]; j++) {
resultArray[k++] = i;
}
}
return resultArray;
}
计数排序法有一个很大的缺点这就导致了很少有使用计数排序法的，假设最小值远大于0，这时候我们可以使用一个偏移量解决，但是如果最小值和最大值之间的范围比较大，那么创建的数组耗费的空间比较大，而且计数排序法只能适用于整数，局限性太大，大家就看看了解这个思路就好。
🔊 时间复杂度
计数排序是一种很简单的排序算法，其经历了两次单for循环，和一次for循环嵌套，所以示例过程中的计数排序法的时间复杂度为O(n2)，但是计数排序存在一种优化方案，在优化方案中会优化掉双重for循环，所以优化后的计数排序是O(N+M)。计数排序的优化方案就不讲了，挺简单的，自己百度看一下就行了。
🔊 稳定性
计数排序排序前后是稳定的。
基数排序是对快速排序的一种演变，上面提到快速排序有一个问题，就是数组的最大值和最小值之间的差值太大，基数排序是将数组的每一位按照顺序分别进行多遍计数排序，最终达到完整排序效果。
看一下演示图就明白了，注意图中标红的表示当前正在计数排序的位数：
🔊 下面看一下代码实现
public static int[] sort(int[] array) {
if (array.length < 2) return array;
//获取数组中的最大值，计算数据的最大位数
int max = array[0];
for (int temp : array) {
if (temp > max) {
max = temp;
}
}
//获取最大值的长度
int maxDigit = (max + "").length();
/** 初始化创建桶，根据演示图应该是数组里面放的数组，用list代替了
* 因为Java创建数组需要指定长度，其实用js写最好了
* 10
* 20 41
*int[] 30 31 .... 69
* int[] int[] ... int[]
*/
List<List<Integer>> bucket = new ArrayList<>();
//下标为0到9总共10个平行数组
for (int i = 0; i < 10; i++) {
bucket.add(new ArrayList<>()); //垂直数组
}
int mold = 10; //取模值
//第一层循环，数据位数循环
for (int i = 0; i < maxDigit; i++) {
mold = mold * 10;
//将数据放在桶中
for (int j = 0; j < array.length; j++) {
//取模/(取模/10)获取到对应位数的数组
int num = (array[j] % mold) / (mold / 10);
bucket.get(num).add(array[j]);
}
//排完了各位把数据按照顺序放回去重新组成数组
int index = 0;
for (int k = 0; k < bucket.size(); k++) {
List<Integer> list = bucket.get(k);
for (int m = 0; m < list.size(); m++) {
array[index++] = list.get(m);
}
bucket.get(k).clear();
}
}
return array;
}
🔊 时间复杂度
基数排序采用了多次计数排序，所以基数排序的时间复杂度是O(K*(N+M)），其中K是最大数据的位数。
🔊 稳定性
因为基数排序采用了计数排序作为实现方式，计数排序是稳定的，所以基数排序也是稳定的。
桶排序跟基数排序有点相似，也算是计数排序的一种优化实现吧，但是它不是根据位数的下标来放数据了，而是创建固定数量的数组，将数据按照一定的算法放在数组的对应下标位置(每个下标代表着一个数据区间，如演示图就是把数组按照最大最小差值划分了30个数据区间，如果不太理解的也可以当成某种可以根据元素大小找到对应下标的算法)，出现下标碰撞后再垂直排放，而垂直排放的数组里面是排好序的(桶中存放完数据后会根据排序算法对桶进行排序)。
如果大家对JDK7的HashMap比较了解可以借鉴着理解为这是个有序的HashMap实现，看演示图：
🔊 下面看一下代码实现
public static int[] sort(int[] array) {
//首先获取最大值最小值的差值
int max = array[0];
int min = array[0];
for (int i = 1; i < array.length; i++) {
if (array[i] > max) {
max = array[i];
}
if (array[i] < min) {
min = array[i];
}
}
int diff = max - min;
//初始化桶的长度，这个一般使用数组的长度，减少Hash碰撞次数
int bucketLength = array.length;
List<LinkedList<Integer>> bucket = new ArrayList<LinkedList<Integer>>(bucketLength);
//初始化桶
for (int i = 0; i < bucketLength; i++) {
bucket.add(new LinkedList<Integer>());
}
//将原始数据放在对应桶里面
for (int i = 0; i < array.length; i++) {
//根据当前数据与差值所分配对应范围区间的数组下标中
int num = (int) ((array[i] - min) * (bucketLength - 1) / diff);
bucket.get(num).add(array[i]);
}
//对每个桶内部进行排序
for (int i = 0; i < bucket.size(); i++) {
Collections.sort(bucket.get(i));
}
//将排好序的数据写回原来的数组
int index = 0;
for (int k = 0; k < bucket.size(); k++) {
List<Integer> list = bucket.get(k);
for (int m = 0; m < list.size(); m++) {
array[index++] = list.get(m);
}
}
return array;
}
🔊 时间复杂度
桶排序的时间复杂度计算比较复杂，首先横向数组的排序中时间复杂度为 O(N)，其次结束后每个桶内部出现碰撞后的数组排序根据排序算法来算的，所以其时间复杂度为O(N+N(竖向链表排序时间复杂度))。暂且设置为N次链表的排序的时间复杂度为k。桶排序的时间福再度为O(N+k)，当然这个k可能是O(n2)或者是O(N)之间的范围。那么桶排序最坏的情况是O(n2)，最好的情况是没有碰撞，链表都是1个数，为O(n)
🔊 稳定性
桶排序排序过程中数据是有序的取放，所以桶排序是稳定的。
堆排序是通过二叉堆的方式来实现的，我们知道二叉堆是有序的。其思想是通过先将数组模拟一个完全二叉树，然后再根据节点顺序将节点进行排序，最终形成一个二叉堆。
看一下演示效果：
🔊 下面看一下代码实现
public static int[] sort(int[] array) {
int length = array.length;
if (length < 2) return array;
//先创建一个最大堆
for (int i = (length - 1) / 2; i >= 0; i--) {
adjustHeap(array, i, length);
}
//调整堆结构，堆顶元素与末尾元素进行交换+交换堆顶元素与末尾元素
for (int i = length - 1; i > 0; i--) {
//将堆顶元素与末尾元素进行交换
int temp = array[i];
array[i] = array[0];
array[0] = temp;
//重新调整堆结构
adjustHeap(array, 0, i);
}
return array;
}
private static void adjustHeap(int[] array, int parent, int length) {
//定义最大值的索引
int maxIndex = parent;
//parent为对应元素的位置（数组的索引）
int left = 2 * parent + 1;
int right = 2 * (parent + 1);
//左子节点如果比父节点大
if (left < length && array[left] > array[maxIndex]) {
maxIndex = left;
}
//右子节点如果比父节点大
if (right < length && array[right] > array[maxIndex]) {
maxIndex = right;
}
//maxIndex为父节点，若发生改变则说明不是最大节点，需要交换
if (maxIndex != parent) {
int temp = array[maxIndex];
array[maxIndex] = array[parent];
array[parent] = temp;
//交换之后递归再次调整比较
adjustHeap(array, maxIndex, length);
}
}
🔊 时间复杂度
最大堆的创建过程的时间复杂度为O(n)，堆的调整过程中N次调整的时间复杂度为O(nlogn)，所以最终堆排序的时间复杂度为O(nlogn)。
🔊 稳定性
堆排序过程中存在着相同元素调整的时候被移动尾部，可能会打乱原来的顺序，所以堆排序是不稳定的。
| 排序算法 | 时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n2) | O(n) | O(n2) | O(1) | 稳定 |
| 选择排序 | O(n2) | O(n2) | O(n2) | O(1) | 不稳定 |
| 插入排序 | O(n2) | O(n) | O(n2) | O(1) | 稳定 |
| 希尔排序 | O(n1.3~2) | O(n) | O(n2) | O(1) | 不稳定 |
| 快速排序 | O(n*logn) | O(n*logn) | O(n2) | O(logn) | 不稳定 |
| 归并排序 | O(n*logn) | O(n*logn) | O(n*logn) | O(n) | 稳定 |
| 计数排序 | O(n+k) | O(n+k) | O(n+k) | O(k) | 稳定 |
| 基数排序 | O(n*k) | O(n*k) | O(n*k) | O(n+k) | 稳定 |
| 桶排序 | O(n+k) | O(n+k) | O(n2) | O(n+k) | 稳定 |
| 堆排序 | O(n*logn) | O(n*logn) | O(n*logn) | O(1) | 不稳定 |
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）