基于比较的排序算法基本原理及Java实现
1. 七大基于比较的排序-总览
1.1常见基于比较的排序分类
1.2时间复杂度，空间复杂度以及稳定性。
- 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
- 不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
2.直接插入排序
2.1 直接插入排序的基本思想
直接插入排序的基本思想，就是每次选取一个待排序元素，按照一定规定插入到前面已经排好序的一组元素的适当位置。当每个元素都插入完毕，整个序列已经有序。
当插入第i(i >= 1)时，前面的V[0]，V[1]，……，V[i-1]已经排好序。这时，用V[I]的排序码与V[i-1]，V[i-2]，…的排序码顺序进行比较，找到插入位置即将V[i]插入，原来位置上的元素向后顺移。
2.2 直接插入排序动画演示
2.3 代码示例
public static void insertSort(int[] arr){
for(int i=1;i<arr.length;i++){//从第二个元素开始，遍历整个数组
int j=i-1;//i之前的序列 已经有序
int temp=arr[i];
for(;j>=0;j--){//此循环用于寻找插入位置
if(arr[j]>temp){//此时逐个向后移动元素
arr[j+1]=arr[j];
}else break;//找到插入位置 直接break
}
arr[j+1]=temp;//直接插入
}
}
2.4 时间复杂度，空间复杂度以及稳定性
- 时间复杂度最坏情况：数组整体逆序O(n^2);
- 时间复杂度最好情况：数组已经有序O(n^2);
- 空间复杂度:O(1);
- 稳定性：稳定;
3. 希尔排序
3.1 算法思想
希尔排序是特殊的插入排序，直接插入排序每次插入前的遍历步长为1，而希尔排序是将待排序列分为若干个子序列，对这些子序列分别进行直接插入排序，当每个子序列长度为1时，再进行一次直接插入排序时，结果一定是有序的。常见的划分子序列的方法有：初始步长（两个子序列相应元素相差的距离）为要排的数的一半，之后每执行一次步长折半。
3.2 图片演示
3.3 代码示例
public static void hell(int[] arr,int gap){//当gap=1时 其实就是直接插入排序
for(int i=gap;i<arr.length;i++){
int j=i-gap;
int temp=arr[i];
for(;j>=0;j-=gap){
if(arr[j]>temp){
arr[j+gap]=arr[j];
}else break;
}
arr[j+gap]=temp;
}
}
public static void hellSort(int[] arr){
int gap=arr.length;
while(gap>1){
gap=gap/2+1;
hell(arr,gap);
}
}
3.4 时间复杂度，空间复杂度以及稳定性
- 时间复杂度最好：O(n);
- 时间复杂度最坏：O(n^1.5);
- 时间复杂度平均：O(n^1.3);
- 空间复杂度：O(1);
- 稳定性：不稳定;
4.选择排序
4.1 算法思想
选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
4.2 动画演示
4.3 代码示例
public static void selectSort(int[] arr){
for(int i=0;i<arr.length;i++){
for(int j=i+1;j<arr.length;j++){
if(arr[j]<arr[i]){
int temp=arr[j];
arr[j]=arr[i];
arr[i]=temp;
}
}
}
}
4.4 时间复杂度，空间复杂度以及稳定性
- 时间复杂度最好：O(n);
- 时间复杂度最坏：O(n^2;
- 时间复杂度平均：O(n^2);
- 空间复杂度：O(1);
- 稳定性：不稳定;
5.堆排序
5.1 算法思想
堆
堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。如下图：
- 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
- 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
- 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
5.2 动画演示
5.3 代码示例
public static void heapSort(int[] arr){//排序方法
creatHeap(arr);
int end=arr.length-1;
//因为是大根堆，所以根节点值为最大值，根节点与最后一个节点值交换 输出并删除此时最后一个节点，然后向下调整根节点
while(end>0){
int temp=arr[0];
arr[0]=arr[end];
arr[end]=temp;
shiftDown(arr,0,end);
end--;
}
}
public static void creatHeap(int[] arr){//建堆
for(int parent=(arr.length-1-1)/2;parent>=0;parent--){
shiftDown(arr,parent,arr.length);
}
}
public static void shiftDown(int[]arr,int root,int len){//向下调整操作
int parent=root;
int child=parent*2+1;
while(child<len){
if(child+1<len&&arr[child]<arr[child+1]){//待调整节点右子树大于左子树
child++;
}
if(arr[child]>arr[parent]){//由于是大根堆，如果儿子节点值大于父亲节点就交换
int temp=arr[parent];
arr[parent]=arr[child];
arr[child]=temp;
parent=child;//继续向下调整，防止调整后不满足大根堆的条件
child=parent*2+1;
}else break;
}
}
5.4 时间复杂度，空间复杂度以及稳定性
- 时间复杂度最好：O(nlogn);
- 时间复杂度最坏：O(nlogn);
- 时间复杂度平均：O(nlogn);
- 空间复杂度：O(1);
- 稳定性：不稳定;
6.冒泡排序
6.1 算法思想
比较两个相邻的元素，将值大的元素交换到右边
思路：依次比较相邻的两个数，将比较小的数放在前面，比较大的数放在后面。
- 1.第一次比较：首先比较第一和第二个数，将小数放在前面，将大数放在后面。
- 2.比较第2和第3个数，将小数 放在前面，大数放在后面。
- 3.如此继续，知道比较到最后的两个数，将小数放在前面，大数放在后面，重复步骤，直至全部排序完成
- 4.在上面一趟比较完成后，最后一个数一定是数组中最大的一个数，所以在比较第二趟的时候，最后一个数是不参加比较的。
- 5.在第二趟比较完成后，倒数第二个数也一定是数组中倒数第二大数，所以在第三趟的比较中，最后两个数是不参与比较的。
- 6.依次类推，每一趟比较次数减少依次
6.2 动画演示
6.3 代码示例
public static void bubbleSort(int[] arr){
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]){
int temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
flag=true;
}
}
if(flag==false) break;//如果一趟循环走完没有交换，说明已经有序，直接break
}
}
6.4 时间复杂度，空间复杂度以及稳定性
- 时间复杂度最好：O(n);
- 时间复杂度最坏：O(n^2);
- 时间复杂度平均：O(n^2);
- 空间复杂度：O(1);
- 稳定性：稳定
7.快速排序（十分重要）
7.1 算法思想
我们从数组中选择一个元素，我们把这个元素称之为中轴元素吧，然后把数组中所有小于中轴元素的元素放在其左边，所有大于或等于中轴元素的元素放在其右边，显然，此时中轴元素所处的位置的是有序的。也就是说，我们无需再移动中轴元素的位置。
从中轴元素那里开始把大的数组切割成两个小的数组(两个数组都不包含中轴元素)，接着我们通过递归的方式，让中轴元素左边的数组和右边的数组也重复同样的操作，直到数组的大小为1，此时每个元素都处于有序的位置。
7.2 动画演示
7.3 代码示例
//该代码参考acwing创始人yxc的快排模板
public static void quickSort(int[] arr,int l,int r){
if(l>=r) return;//每次判断传进来左右下标
int i=l-1,j=r+1;//因为在循环中，要先i++，j--所以i，j定义为两边界偏移1
int x=arr[(l+r)/2];//取x为数组中间位置数
while(i<j){
do i++;while(arr[i]<x);
do j--;while(arr[j]>x);
//此时i指向的数字大于中轴数字， j指向数字小于中轴数字 交换
if(i<j){
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
quickSort(arr,l,j);//退出循环是i==j 递归排序
quickSort(arr,j+1,r);
}
7.4 时间复杂度，空间复杂度以及稳定性
- 时间复杂度最好：O(nlog2n);
- 时间复杂度最坏：O(n^2);
- 时间复杂度平均：O(nlog2n);
- 空间复杂度：O(nlog2n);
- 稳定性：不稳定;
8.归并排序
8.1 算法思想
将一个大的无序数组有序，我们可以把大的数组分成两个，然后对这两个数组分别进行排序，之后在把这两个数组合并成一个有序的数组。由于两个小的数组都是有序的，所以在合并的时候是很快的。
通过递归的方式将大的数组一直分割，直到数组的大小为 1，此时只有一个元素，那么该数组就是有序的了，之后再把两个数组大小为1的合并成一个大小为2的，再把两个大小为2的合并成4的 …… 直到全部小的数组合并起来。
8.2 动画演示
8.3 代码示例
public static void mergerSort(int[]arr){
mergerSortInternal(arr,0,arr.length-1);
}
public static void mergerSortInternal(int[]arr,int l,int r) {//
if (l >= r) return;
int mid = (l + r) / 2;//把数组分为两个
mergerSortInternal(arr, l, mid);//对左边数组递归排序
mergerSortInternal(arr, mid + 1, r);//对右边数组递归排序
merge(arr,l,mid,r);//排序完成，进行合并
}
public static void merge(int[]arr,int low,int mid,int high){
int s1=low;//mid左侧数组的头和尾
int e1=mid;
int s2=mid+1;//mid右侧数组的头和尾
int e2=high;
int[]temp=new int[high-low+1];//定义一个数字，用来合并他们
int k=0;//指示数组下标
while(s1<=e1&&s2<=e2){//选出两侧数组最小元素 插入temp数组
if(arr[s1]<=arr[s2]) temp[k++]=arr[s1++];
else temp[k++]=arr[s2++];
}
while(s1<=e1) temp[k++]=arr[s1++];//如果一侧数组插入完毕，另一侧还有剩余，则全部插入
while(s2<=e2) temp[k++]=arr[s2++];
for(int i=0;i<temp.length;i++){//返还到arr数组
arr[i+low]=temp[i];
}
}
}
8.4 时间复杂度，空间复杂度以及稳定性
- 时间复杂度最好：O(nlog2n);
- 时间复杂度最坏：O(nlog2n);
- 时间复杂度平均：O(nlog2n);
- 空间复杂度：O(n);
到此这篇关于Java数据结构之基于比较的排序算法基本原理及具体实现的文章就介绍到这了,更多相关Java 排序算法内容请搜索服务器之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持服务器之家！
原文链接：https://blog.csdn.net/m0_52276165/article/details/120211146
