Java数据结构之基于比较的排序算法基本原理及具体实现

基于比较的排序算法基本原理及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);

来源：https://blog.csdn.net/m0_52276165/article/details/120211146