【轻松掌握数据结构】排序算法深度解析

排序算法

文章目录

• 排序算法
• 前言
• 一、直接插入排序
• • 1.概念
  • 2.代码演示
  • 3.特点
• 二、希尔排序
• • 1.概念
  • 2.代码演示
  • 特点
• 三、直接选择排序
• • 1.概念
  • 2.代码演示
  • 3.特点
• 四、堆排序
• • 1.概念
  • 2.代码演示
  • 3.特点
• 五、冒泡排序
• • 1.概念
  • 2.代码实现
  • 3.特点
• 六、快速排序
• • 1.Hoare版
  • • 1.概念
    • 2.代码实现
  • 2.挖坑法
  • • 1.概念
    • 2.代码实现
  • 3.特点
• 七、归并排序
• • 1.概念
  • 2.代码实现
  • 3.特点
• 八、总结
• 总结

前言

大家好啊，先祝大家期末不挂科！！！！！！今天我们来讲一讲排序～ 所谓排序，就是使⼀串记录，按照其中的某个或某些关键字的⼤⼩，递增或递减的排列起来的 操作。 那有没有一种情况，一个数列中有两个相同大小的数字，在排序过后，他们的相对位置会不会改变？诶～这就涉及到稳定性了！

稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变， 即在原序列，r[i]=r[j]，且r[i]在r[j]之前，⽽在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

OK，现在让我们进入排序算法的学习吧～ 常见排序算法：直接插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序、归并排序。

``

一、直接插入排序

1.概念

从第二个数组元素开始，当前元素比它前一个元素小就交换位置，直到前一个元素比它小为止，每循环一次i++。

2.代码演示

public class ChaSort {

private int[] arr;

@Override
public String toString() {
return "ChaSort{" +
"arr=" + Arrays.toString(arr) +
'}';
}

public ChaSort(int[] arr){
this.arr=arr;
for (int i = 1; i < arr.length; i++) {
for (int j = i–1; j >= 0; j—) {
int jap=arr[j];
int tem=arr[j+1];
if(jap>tem){
swap(arr,j);
}else break;

}
}

}

public void swap(int[] arr,int j){
int tem=arr[j];
arr[j]=arr[j+1];
arr[j+1]=tem;
}
}

3.特点

二、希尔排序

1.概念

与直接插入排序的区别就是它不和i下一个元素比较，是和i+tab为下标的元素比较。tab=len/k，k是自定义的。

从第一个数组元素（i）开始，和隔了tab个下标的元素为一组，一组内二者相互比较，后者小于前者则元素交换，直到一组内前面的小于后面的。每循环一次tab／=k。

注意，要保证tab最后一次会等于1。

2.代码演示

public class HaxSort {
private int[] arr;

@Override
public String toString() {
return "HaxSort{" +
"arr=" + Arrays.toString(arr) +
'}';
}

public HaxSort(int[] arr,int k) {
this.arr = arr;
int len = arr.length;
int tab = len / k;
for (; tab > 0; tab /= k) {

for (int p = 0; p <= len–1–tab ; p++) {
for(int i=p;i>=0 ;i-=tab) {
if (arr[i] > arr[i + tab]) {
swap(arr, i, i + tab);
}else break;
}
}
}
}
public void swap(int[] arr,int a,int b){
int tam=arr[a];
arr[a]=arr[b];
arr[b]=tam;
}

}

特点

冒泡排序加了限制好情况是O(n)

三、直接选择排序

1.概念

顾名思义，选择排序会直接从当前下标i往后遍历数组，选择最小的值与i下标元素进行替换。每循环一次i++。

2.代码演示

public class SelectSort {
private int[] arr;
int min=0;

@Override
public String toString() {
return "SelectSort{" +
"arr=" + Arrays.toString(arr) +
'}';
}

public SelectSort(int[] arr){
this.arr=arr;
for (int j = 0; j < arr.length; j++) {
for (int i = j+1; i < arr.length; i++) {
if(arr[i]<arr[min]){
min=i;
}
}
swap(arr,min,j);

}
}

public void swap(int[] arr,int i,int j){
int tem=arr[i];
arr[i]=arr[j];
arr[j]=tem;
}

}

3.特点

四、堆排序

1.概念

当我们选择升序排列的时候，我们要创建大堆，后让堆顶元素和堆最后一个元素进行交换，len－1，对剩下元素重新建立大堆。重复此过程。

排升序需要建大堆，降序建小堆

2.代码演示

public class HeapSort {
int[] arr;

@Override
public String toString() {
return "HeapSort{" +
"arr=" + Arrays.toString(arr) +
'}';
}

public HeapSort(int[] arr){
this.arr=arr;
int len=arr.length;
for (; len >0 ; len—) {
bigheap(len);
swap(arr,0,len–1);//收尾交换
}
}
public void bigheap(int len){
for (int i = (len–1)/2; i >= 0; i—) {
int lef=i*2+1;
int rig=i*2+2;
if(lef>=len){
continue;
} else if (rig>=len) {
if(arr[lef]>arr[i]){
swap(arr,lef,i);
}else continue;

}else {
int p=arr[lef]>arr[rig]?lef:rig;
if(arr[p]>arr[i]){
swap(arr,i,p);
}
}
}

}

public void swap(int[] arr,int i,int j){
int tem=arr[i];
arr[i]=arr[j];
arr[j]=tem;
}

}

提问：堆排序为什么不能直接用小根堆排序？ 因为小根堆只能保证根是最小的。

3.特点

五、冒泡排序

1.概念

从j下标开始，当前元素与j+1下标元素比较，大则交换元素位置，并且j++，直到这个较大值遇到更大的或到达当前循环最后位置（j < arr.length-i-1），每循环一次i++。

2.代码实现

public class MaoSort {
int[] arr;

@Override
public String toString() {
return "MaoSort{" +
"arr=" + Arrays.toString(arr) +
'}';
}

public MaoSort(int[] arr) {
this.arr=arr;

for (int i = 0; i < arr.length–1; i++) {
for (int j = 0; j < arr.length–i–1; j++) {
if(arr[j]>arr[j+1]){
swap(arr,j);
}
}
}
}
public static void swap(int[] arr,int j){
int tem=arr[j+1];
arr[j+1]=arr[j];
arr[j]=tem;
}

}

3.特点

六、快速排序

快速排序有3个版本：Hoare版、挖坑法、前后指针

1.Hoare版

1.概念

数组最左边为low，右边为high，选择pivot为arr[low]，high左走，找到比pivot小的；low往右走，找到比pivot大的，交换，重复这一步骤，直到二者相遇。

2.代码实现

private static int parttionHoare(int[] array, int low, int high) {
int pivot = array[low];
//记录原来low的下标
int i = low;
while (low < high) {
//这里可不可以不加等号
while (low < high && array[high] >= pivot) {
high—;
}
while (low < high && array[low] <= pivot) {
low++;
}
swap(array, low, high);
}
swap(array,i,low);
return low;
}

思考：为什么不能low先走？

2.挖坑法

1.概念

和hoare不一样的是，它的基准值，也就是坑，是实时的，一边元素移动后，就会留下一个坑，这时候另一边移动，找到补这个坑的值。

2.代码实现

private static int parttion2(int[] array, int low, int high) {
int tmp = array[low];

while (low < high) {
while (low < high && array[high] >= tmp) {
high—;
}
array[low] = array[high];

while (low < high && array[low] <= tmp) {
low++;
}
array[high] = array[low];
}

array[low] = tmp;
return low;
}

思考：为什么要有“=”？没有会怎么样？

3.特点

七、归并排序

1.概念

一组元素，最左边下表为lef，右边为rig，中间为min=(lef+rig)/2,先递归左部分，也就是lef和min之间，再递归右部分min和rig，直到rig<=lef为止。左右两边递归返回后，进入大小比较环节，传入lef,min,rig，让元素从lef和min发别开始比较，小的进入新建的数组。程序直到递归结束。

人话：把数组分成多份，每份再分成多个小份，小份之间排序完后，大份里面再排序

2.代码实现

（1）递归版

public class BackSort {
private int[] arr;

@Override
public String toString() {
return "BackSort{" +
"arr=" + Arrays.toString(arr) +
'}';
}

public BackSort(int[] arr,int lef,int rig) {
this.arr = arr;
back(arr,lef,rig);
}
public void back(int[] arr,int lef,int rig){
int min=(rig+lef)/2;
if(rig<=lef){
return;
}
back(arr,lef,min);
back(arr,min+1,rig);
gui(arr,lef,min,rig);
}
public void gui(int[] arr,int lef,int min,int rig){
int[] tem=new int[rig–lef+1];
int k=0;
int i=lef;
int j=min+1;
while (i<=min&&j<=rig){
tem[k++]=arr[i]<arr[j]?arr[i++]:arr[j++];
}
while(i<=min){
tem[k++]=arr[i++];
}
while (j<=rig){
tem[k++]=arr[j++];
}
for (int l = 0; l < tem.length; l++) {
arr[lef+l]=tem[l];
}
}

}

（2）非递归版

public BackSort(int[] arr,int lef,int rig) {
this.arr = arr;
//递归
//back(arr,lef,rig);
//非递归
back(arr);

}
//非递归
public void back(int[] arr) {
int gap=1;
while(gap < arr.length) {
for (int i = 0; i < arr.length; i += 2*gap) {
int lef = i;
int min =lef+gap–1;
int rig=min+gap;
if (rig >= arr.length) {
rig = arr.length – 1;
}

if (min >= arr.length) {
min = arr.length – 1;
}
gui(arr, lef, min, rig);
}
gap *= 2;
}
}

3.特点

八、总结

总结

今天讲了七种排序算法，最重要的是快排！大家一定要多做一点题！ 最后祝大家期末不挂科！大家期末不挂科！大家期末不挂科！（重要的事情说三遍！！！！） 我们期末后见~