🧧🧧🧧🧧🧧个人主页🎈🎈🎈🎈🎈
🧧🧧🧧🧧🧧数据结构专栏🎈🎈🎈🎈🎈
🧧🧧🧧🧧🧧【数据结构】优先级队列——堆🎈🎈🎈🎈🎈
文章目录
- 1. 排序的概念及引用
- 1.1 排序的概念
- 1.2常见排序
- 2. 常见排序算法的实现
- 2.1 插入排序
- 2.2希尔排序
- 2.3选择排序
- 2.4堆排序
- 2.5冒泡排序
- 2.6快速排序
- 2.7归并排序
- 3.排序算法复杂度及稳定性总结
1. 排序的概念及引用
1.1 排序的概念
排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
内部排序：数据元素全部放在内存中的排序。
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。
1.2常见排序
2. 常见排序算法的实现
2.1 插入排序
2.1.1基本思想：
直接插入排序是一种简单的插入排序法，其基本思想是：
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。实际中我们玩扑克牌时，就用了插入排序的思想。
2.1.2思路分析
大前提：
1.我们定义一个tmp临时变量
2.定义两个指针一个i一个j，i从第二个开始，j = i -1.
1.遍历这个数组，将i下标的数值先放入tmp临时变量
2.由j下标的值与tmp中的值比较
2.1array[j] > tmp
将j下标的值放入j+1下标，然后j-1下标的值再去与tmp的值进行比较，重复这个过程，直到j下标越界，跳出这个循环
2.2array[j] < tmp
直接将tmp的值放入j+1下标中，说明j下标之前的值都是有序的
2.1.3绘图分析
2.1.4代码实现
/**
* 直接插入排序
* 时间复杂度 0(n^2)
* 空间复杂度 O(1)
* 稳定性：稳定的
* @param array
*/
public static void insertSort(int[] array) {
//从数组的第二个数开始比较
for (int i = 1; i < array.length; i++) {
//将i下标的元素放入临时变量tmp中
int tmp = array[i];
int j = i-1;
//j是从i-1开始
for (; j >=0 ; j--) {
//比较j下标的值与tmp的值
if(array[j] > tmp) {
//array[j] > tmp
array[j+1] = array[j];
} else {
//array[j] < tmp
break;
}
}
//走到这里说明要么就是array[j] < tmp 要么就是j不满足条件
array[j+1] = tmp;
}
}
2.2希尔排序
2.2.1基本思想
先选定一个整数，把待排序文件中所有记录分成多个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序
2.2.2思路分析
假设数组中一共有N个数
1.先确定gap（组数），有很多种分组的方式，我举几个例子，分别为gap = N/2 和 gap = N/3+1,gap越大，组中的数据越小，一般采取跳跃式分组，这样可以使组中的数据小的放在前面，大的放在后面。
2.采取直接插入排序
3.采取直接插入排序时，i定义为gap，j定义为i-gap而每一次i++加1即可，不需要加gap，这样使得gap组可以同时进行，j在回退的过程中不能j–，必须j-=gap。
2.2.3绘图分析
2.2.4代码实现
/**
* 希尔排序
* 时间复杂对 O(n^2)
* 空间复杂度 O(1)
* 稳定性：不稳定
* @param array
*/
public static void shellSort(int[] array) {
//确定分组
int gap = array.length;
while(gap > 1) {
gap /= 2;
insertSort1(array,gap);
}
}
private static void insertSort1(int[] array,int gap) {
//从数组的第二个数开始比较
for (int i = gap; i < array.length; i++) {
//将i下标的元素放入临时变量tmp中
int tmp = array[i];
int j = i-gap;
//j是从i-1开始
for (; j >=0 ; j -= gap) {
//比较j下标的值与tmp的值
if(array[j] > tmp) {
//array[j] > tmp
array[j+gap] = array[j];
} else {
//array[j] < tmp
break;
}
}
//走到这里说明要么就是array[j] < tmp 要么就是j不满足条件
array[j+gap] = tmp;
}
}
注意：此处的gap直接会影响这个排序的时间复杂度。
2.3选择排序
2.3.1基本思想
每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。
2.3.2思路分析
大前提：
1.需要两个指针i，j来遍历这个数组
2.需要一个临时变量minIndex来存储数组中最小值的下标
思路分析：
1.i从0下标开始，先将i下标存储再minIndex中
2.j从i+1开始向后遍历，再遍历的过程中与minIndex下标的值比较，小于则更新minIndex之后j++，大于则直接j++
3.找到了这个数组最小值的下标，此时minIndex就是最小值的下标，然后将与i下标的值进行交换然后i++，重复上述步骤直到数组有序
2.3.3绘图分析
2.3.4代码实现
/**
* 选择排序
* 时间复杂对 O(n^2)
* 空间复杂度 O(1)
* 稳定性：不稳定
* @param array
*/
public static void selectSort1(int[] array) {
for (int i = 0; i < array.length; i++) {
//先将i的下标存储再minIndex中
int minIndex = i;
for (int j = i+1; j <array.length; j++) {
if(array[j] <array[minIndex]) {
//通过遍历j来判断是否小于minIndex下标的值，小于则更新minIndex的值
minIndex = j;
}
}
//找到了最小的值再交换
swap(array,minIndex,i);
}
}
private static void swap(int[] array,int x,int y) {
int tmp = array[x];
array[x] = array[y];
array[y] = tmp;
}
2.4堆排序
2.4.1基本思想
堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆
来进行选择数据。
这个就不详细写了，上一篇文章堆中讲述了堆排序的实现，这里我们直接上代码吧。
2.4.2代码实现
/**
* 堆排序:
* 时间复杂度：O(N*logN)
* 空间复杂度：O(1)
* 稳定性：不稳定的排序
* @param array
*/
public static void heapSort(int[] array){
//创建大根堆
createHeap(array);
int end = array.length-1;
while (end > 0) {
swap(array,0,end);
siftDown(array,0,end);
end--;
}
}
private static void createHeap(int[] array) {
for (int parent = (array.length-1-1)/2; parent >= 0 ; parent--) {
siftDown(array,parent,array.length);
}
}
private static void siftDown(int[] array,int parent,int len) {
int child = (2*parent)+1;
while (child < len) {
if(child + 1 < len && array[child] < array[child+1]) {
child = child+1;
}
if(array[child] > array[parent]) {
swap(array,child,parent);
parent = child;
child = 2*parent+1;
}else {
break;
}
}
}
2.5冒泡排序
2.5.1基本思想
对无序序列中相邻记录关键字的比较和位置的交换，使关键字较小的记录向一端漂移，而关键字较大的记录则向另一端下沉，直至形成有序序列。
2.5.2思路分析
冒泡排序算法通过重复地走访需要排序的元素列，依次比较两个相邻的元素，如果它们的顺序错误（如逆序），则将它们交换。这个过程一直重复，直到没有相邻元素需要交换为止，此时序列已经排序完成。这种排序算法的名字来源于其工作原理：较小的元素像气泡一样逐渐“浮”到数列的顶端，较大的元素则逐渐“沉”到底部。
2.5.3代码实现
/**
* 不带优化的情况下：
* 时间复杂度：
* 最好和最坏 都是O(N^2)
* 空间复杂度：O(1)
* 稳定性：稳定的
* @param array
*/
public static void bubbleSort(int[] array) {
//i代表趟数 10 -》 9趟
for (int i = 0; i < array.length-1; i++) {
boolean flg = false;
for(int j = 0;j < array.length-1-i;j++) {
if(array[j] > array[j+1]) {
swap(array,j,j+1);
flg = true;
}
}
//没有交换证明有序了
if(flg == false) {
return;
}
}
}
2.6快速排序
2.6.1基本思想
任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
2.6.2思路分析
1.选择基准：在待排序列中，按照某种方式挑出一个元素，作为 “基准”（pivot）
2.分割操作：以该基准在序列中的实际位置，把序列分成两个子序列。此时，在基准左边的元素都比该基准小，在基准右边的元素都比基准大
3.递归地对两个序列进行快速排序，直到序列为空或者只有一个元素。
如何选择基准(pivot)？
一般我们采取固定法，取序列的第一个或最后一个元素作为基准。
如下图实现：
将区间按照基准值划分为左右两半部分的常见方式有：
1.Hoare法
2.挖空法
注意：在选择这两种方法的时候一般优先挖空法。
2.6.3代码实现
Hoare法
//Hoare法
private static int partitionHoare(int[] array,int left,int right) {
//定基准
int tmp = array[left];
//记录基准的下标s
int s = left;
while(left < right) {
//以左边为基准时，需要right先移动，left后移动。
// 原因：如果你left先移动，就会出现与基准的大的数交换，那么就不能保证基准的左边都比基准小，右边比基准大。
//array[right] >= tmp 加等号的目的是基准是right下标的值，如果没有等于号，那么会将基准更换
while(left < right && array[right] >= tmp) {
right--;
}
//array[left] <= tmp 加等号的目的是基准是left下标的值，如果没有等于号，那么会将基准更换
while(left < right && array[left] <= tmp) {
left++;
}
//满足left下标大于tmp并且right下标小于tmp，交换两下标的值
swap(array,left,right);
}
//说明left与right相遇了，将该下标的值与tmp交换
swap(array,s,left);
return left;
}
2.挖空法
private static int partition(int[] array,int left,int right) {
//将基准存储在tmp中
int tmp = array[left];
while(left < right) {
//以左边为基准时，需要right先移动，left后移动。
// 原因：如果你left先移动，就会出现与基准的大的数交换，那么就不能保证基准的左边都比基准小，右边比基准大。
//array[right] >= tmp 加等号的目的是基准是right下标的值，如果没有等于号，那么会将基准更换
while(left < right && array[right] >= tmp) {
right--;
}
//说明array[right] < tmp 则交换
array[left] = array[right];
//array[left] <= tmp 加等号的目的是基准是left下标的值，如果没有等于号，那么会将基准更换
while(left < right && array[left] <= tmp) {
left++;
}
//说明array[left] > tmp 则交换
array[right] = array[left];
}
//说明left与right相遇了，将tmp值放入left下标即可。
array[left] = tmp;
return left;
}
2.6.4对快速排序的优化
- 三数取中法选key
最佳的划分是将待排序的序列分成等长的子序列，最佳的状态我们可以使用序列的中间的值，也就是第N/2个数。可是，这很难算出来，并且会明显减慢快速排序的速度。这样的中值的估计可以通过随机选取三个元素并用它们的中值作为枢纽元而得到。事实上，随机性并没有多大的帮助，因此一般的做法是使用左端、右端和中心位置上的三个元素的中值作为枢纽元。
代码实现：
//三数取中法
private static int midNum(int[] array,int left,int right) {
int mid = left + ((right-left) >> 1);
if(array[left] < array[right]) {
if(array[mid] < array[left]) {
return left;
}
if(array[mid] > array[right]) {
return right;
}
}
if(array[left] > array[right]) {
if(array[mid] >array[left]) {
return left;
}
if(array[mid] <array[right]) {
return right;
}
}
return mid;
}
- 递归到小的子区间时，可以考虑使用插入排序
当递归到了小的子区间，序列中的数据越来越趋于有序，则可以采取直接插入排序加快排序速度
代码实现：
if(end - start +1 <=10) {
insertSort3(array,start,end);
return;
}
快速排序全部代码：
/**
* 快速排序
* 时间复杂度：最好情况下：O(N*logN)
* 最坏情况下：O(N^2) 有序 / 逆序（变成冒泡排序）
* 空间复杂度：最好情况下：O(logN)
* 最坏情况下：O(N)
* 稳定性：不稳定的
* @param array
*/
public static void quickSort(int[] array) {
quick(array,0,array.length-1);
}
private static void quick (int[] array ,int start ,int end) {
//1.递归条件
if(start >= end) {
return;
}
//2.找基准
//优化1： 面对数组有序的情况下，该优化有很大的意义，加快了运行时间
//index是取数组array 0下标 中间下标 最后一个下标中值第二大的下标
int index = midNum(array,start,end);
//将该下标换到数组0下标，并以该下标为基准。
swap(array,start,index);
//优化2：在数组趋于有序的情况下，采取直接插入排序，可以加快运行时间
if(end - start +1 <=10) {
insertSort3(array,start,end);
return;
}
//int midIndex = partitionHoare(array,start,end);
int midIndex1 = partition(array,start,end);
//3.递归左右
/*quick(array,start,midIndex-1);
quick(array,midIndex+1,end);*/
quick(array,start,midIndex1-1);
quick(array,midIndex1+1,end);
}
public static void insertSort3(int[] array ,int start,int end) {
for (int i = start+1; i <= end; i++) {
int tmp = array[i];
int j = i-1;
//j是从i-1开始
for (; j >=0 ; j--) {
//比较j下标的值与tmp的值
if(array[j] > tmp) {
//array[j] > tmp
array[j+1] = array[j];
} else {
//array[j] < tmp
break;
}
}
//走到这里说明要么就是array[j] < tmp 要么就是j不满足条件
array[j+1] = tmp;
}
}
//Hoare法
/* private static int partitionHoare(int[] array,int left,int right) {
//定基准
int tmp = array[left];
//记录基准的下标s
int s = left;
while(left < right) {
//以左边为基准时，需要right先移动，left后移动。
// 原因：如果你left先移动，就会出现与基准的大的数交换，那么就不能保证基准的左边都比基准小，右边比基准大。
//array[right] >= tmp 加等号的目的是基准是right下标的值，如果没有等于号，那么会将基准更换
while(left < right && array[right] >= tmp) {
right--;
}
//array[left] <= tmp 加等号的目的是基准是left下标的值，如果没有等于号，那么会将基准更换
while(left < right && array[left] <= tmp) {
left++;
}
//满足left下标大于tmp并且right下标小于tmp，交换两下标的值
swap(array,left,right);
}
//说明left与right相遇了，将该下标的值与tmp交换
swap(array,s,left);
return left;
}*/
//挖坑法
private static int partition(int[] array,int left,int right) {
//将基准存储在tmp中
int tmp = array[left];
while(left < right) {
//以左边为基准时，需要right先移动，left后移动。
// 原因：如果你left先移动，就会出现与基准的大的数交换，那么就不能保证基准的左边都比基准小，右边比基准大。
//array[right] >= tmp 加等号的目的是基准是right下标的值，如果没有等于号，那么会将基准更换
while(left < right && array[right] >= tmp) {
right--;
}
//说明array[right] < tmp 则交换
array[left] = array[right];
//array[left] <= tmp 加等号的目的是基准是left下标的值，如果没有等于号，那么会将基准更换
while(left < right && array[left] <= tmp) {
left++;
}
//说明array[left] > tmp 则交换
array[right] = array[left];
}
//说明left与right相遇了，将tmp值放入left下标即可。
array[left] = tmp;
return left;
}
//三数取中法
private static int midNum(int[] array,int left,int right) {
int mid = left + ((right-left) >> 1);
if(array[left] < array[right]) {
if(array[mid] < array[left]) {
return left;
}
if(array[mid] > array[right]) {
return right;
}
}
if(array[left] > array[right]) {
if(array[mid] >array[left]) {
return left;
}
if(array[mid] <array[right]) {
return right;
}
}
return mid;
}
2.7归并排序
2.7.1基本思想
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and
Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使
子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
2.7.2思路分析
1.分解 将数组递归地分解成较小的子数组，直到子数组只包含一个元素。
2.合并 将相邻的子数组合并成较大的有序数数组。在合并过程中，比较两个有序数组合并成一个更大的有序数组。
3.递归 递归地应用分解和合并步骤，直到所有子数组被合并成一个完整的有序数组。
2.7.3绘图分析
2.7.4代码实现
/**
* 归并排序
* 时间复杂度：O(n*logN)
* 空间复杂度：O(N)
* 稳定性：稳定的
*/
public static void mergeSort(int[] array) {
mergeFunc(array,0,array.length-1);
}
private static void mergeFunc(int[] array,int left,int right) {
if(left >= right) {
return;
}
int mid = left + ((right-left) >> 1);
mergeFunc(array,left,mid);
mergeFunc(array,mid+1,right);
//左边分解完，右边分解完，开始合并
merge(array,left,mid,right);
}
private static void merge(int[] array,int left,int mid,int right) {
int s1 = left;
int e1 = mid;
int s2 = mid+1;
int e2 = right;
int[] tmpArr = new int[right-left+1];
int k = 0;
//1.保证两个表 都有数据
while (s1 <= e1 && s2 <= e2) {
if(array[s1] <= array[s2]) {
tmpArr[k++] = array[s1++];
}else {
tmpArr[k++] = array[s2++];
}
}
//2. 看哪个数组 还有数据 拷贝回去
while (s1 <= e1) {
tmpArr[k++] = array[s1++];
}
while (s2 <= e2) {
tmpArr[k++] = array[s2++];
}
//3.拷贝到源数组
for (int i = 0; i < k; i++) {
array[i+left] = tmpArr[i];
}
}
3.排序算法复杂度及稳定性总结
总结：希望大家可以从我的文章中学到东西，希望大家可以留下点赞收藏加关注🎉🎉🎉🎉🎉
