【一起来学java数据结构】——排序

文章目录

• 【一起来学java数据结构】——排序
• 一、概念
• • 各种常见排序
  • 稳定性
  • 各种排序的稳定性
• 二、插入排序
• • 简单插入排序
• 三、希尔排序
• 四、选择排序
• 五、堆排序
• 六、冒泡排序
• 七、快速排序
• • 优化
  • • 基准值的优化
    • 和基准相同的数据
    • 数据少的时候直接使用插入排序
  • 使用非递归
• 八、归并排序
• • 非递归
• 九、非比较排序
• • 基数排序
  • 桶排序
  • 计数排序

一、概念

各种常见排序

稳定性

对于一组数中的相同的一些相同的数据，如果排序后这些相同的数据的前后顺序没有改变的话，就是稳定的。

判断是否稳定的元素就是元素是否是具有跳跃性的

各种排序的稳定性

二、插入排序

简单插入排序

将数字分为已排序部分和未排序部分，对于每一个要排序的数字来说，和已排序的部分进行比较，直到找到适合它的位置的时候。

public static void insertSort(int[] array){
    for(int i=1;i<array.length;i++){
        int j=i-1;
        int tmp=array[i];
        for(;j>=0;j--){
            if(array[j]>tmp)
                array[j+1]=array[j];
            else
                //如果tmp比它大，就可以跳出循环了
                break;
        }
        array[j+1]=tmp;
    }
}

时间复杂度：最坏的情况：O(n^{2);最好的情况：O(n),所以时间复杂度就是O(n}2)

空间复杂度：O(1)

是稳定的排序

使用场景：数据量不多，而且数据趋于有序的时候

三、希尔排序

希尔排序是插入排序的进阶版，只是将原来的一组元素分为了很多个组，每个组里面进行插入排序。

对于希尔排序来说，要先进行预排序。先进行不同的间隔的排序，最后一次才是间隔为1的普通的插入排序。

public static void shell(int[] array,int gap){
    //同时进行不同组的排序
    for(int i=1;i<array.length;i++){
        int j=i-gap;
        int tmp=array[i];
        //每次的移动距离就是gap
        for(;j>=0;j-=gap){
            if(array[j]>tmp)
                array[j+gap]=array[j];
            else
                break;
        }
        array[j+gap]=tmp;
    }
}
public static void shellSort(int[] array){
    int gap=array.length;
 	//预排序
    while(gap>1){
        shell(array,gap);
        gap/=3+1;
    }
    //最后一次gap为1的插入排序
    shell(array,1);
}

时间复杂度：O(n^1.3)~O(N1.5)

空间复杂度：O（1）

不稳定

四、选择排序

选择排序就是每次循环都选出来一个最小的元素。

未优化版：

//未优化版：每次循环的时候：找到最小的值和别的值比，如果小就让它为最小值再根其他的值比较
public static void selectSort(int[] array){
    for (int i = 0; i < array.length; i++) {
        for (int j = i+1; j <array.length ; j++) {
            //如果j下标的元素比i小，那么两个就交换
            if(array[j]<array[i]){
                int tmp=array[j];
                array[j]=array[i];
                array[i]=tmp;
            }
        }
    }
}

优化版

每次遍历的时候，不是找到比目标值小的就交换了，而是遍历整个之后找到最小的那个之后，才进行最终的交换

//优化版：每次循环就是找到该位置上的元素，所以每次循环的时候找到其中最小的元素
public static void selectSort2(int[] array){
    for (int i = 0; i < array.length; i++) {
        int minIndex=i;
        for (int j = i+1; j <array.length ; j++) {
            if(array[j]<array[minIndex]){
                minIndex=j;
            }
        }
        swap(array,i,minIndex);
    }
}

时间复杂度：O(n^2)

空间复杂度：O(1)

稳定性：稳定

五、堆排序

堆排序先是建堆，然后是交换首位节点，接着向下进行调整

//向下调整
public static void shiftDown(int parent,int[] array,int len){
    int child=2*parent+1;
    while(child<len){
        if(child+1<len&&array[child+1]>array[child]){
            child++;
        }
        if(array[parent]<array[child]){
            swap(array,parent,child);
            parent=child;
            child=2*parent+1;
        }
        else
            break;
    }
}
//建堆
public static void creatHeap(int[] array){
    for (int i = (array.length-1-1)/2; i >=0 ; i--) {
        shiftDown(i,array,array.length);
    }
}
public static void heapSort(int[] array){
    //建堆
    creatHeap(array);
    int end=array.length-1;
    while(end>0){
        swap(array,0,end);
        shiftDown(0,array,end);
        end--;
    }
}

时间复杂度O(n*logn)

空间复杂度O(1)

不稳定

六、冒泡排序

比较每一个相邻的元素，如果第一个比第二个大，就交换，比较的结果是最大的元素到达末尾

然后再次进行上面的比较，除了最后一个元素。

之后就是越来越少的元素参与此比较，直到没有元素参与。

public static void bubbleSort(int[] array){
    //外面的for循环是：进行数组长度-1次冒泡排序
    for(int i=0;i<array.length-1;i++){
        //内部的for循环是：进行array.length-1-i次交换
        boolean flag=false;
        for (int j = 0; j < array.length-1-i; j++) {
            if(array[j+1]<array[j]) {
                swap(array, j, j + 1);
                flag = true;
            }
        }
        if(!flag)
            break;
    }
}

时间复杂度：O(n^2)

空间复杂度：O(1)

稳定，因为都是相连的交换，没有跳跃的交换

七、快速排序

算法思路：

快速排序是某一个关键字的数都小于该数，右边的数都大于该数。

然后再以同样的方式处理该数的左边和右边

直到左边和右边的数的长度变成了0或1

public static void quick(int[] array,int left,int right){
    if(left>=right)
        return;
    int prvot=partition(array,left,right);
 	//处理左边
    quick(array,left,prvot-1);
    //处理右边
    quick(array,prvot+1,right);
}

所以问题的关键就变成了找到每个数组的关键字，下面有几种方法可以使用

1. 方法一：马上交换

将数组的第一个元素作为是整个数组要比较的元素，存入tmp中，分别定义两个数一个left，一个right，

先从right开始向左走，如果该数大于等于tmp，rightt继续向左走；如果left>right或该数小于tmp就将该数存于array[left]中，并停止rigth的移动

接着从left开始向右走，如果该数小于等于tmp，left继续向右走；如果left>right或该数大于tmp就将该数存于array[right]中，并停止left的移动

重复上面的两个步骤，直到left等于right是为止。

此时有一个小问题：如果是大于tmp或小于tmp，不叫等于号可不可以？

答案是不可以，如果数组中有相同的数据，就会出现重复的在array[left]和array[right]中反复移动的情况

3 5 1 4 3 6 3 5 1 4 3 6

l r l r

所以就会在l和r之间反复移动，造成死循环

2. 方法二：后来交换

和上面的right走完不等left走完就马上交换相比，这个方法是left和right同时退出循环之后再进行交换。

大体方法和方法一差不多，具体的差别请看下面的代码

public static int partition(int[] array,int left,int right){
    int tmp=array[left];
    int l=left;
    int r=right;
    while(l<r){
        while (l<r&&array[r]>=tmp) r--;
        while (l<r&&array[l]<=tmp) l++;
        swap(array,l,r);
    }
    swap(array,l,left);
    return l;
}

快速排序的复杂度分析

对于快速排序来说，有些像二叉树。

每一层的加一起的比较次数是N，高度是O(logN)

所以时间复杂度是O(N*logN)

对数字的敏感度：

当数字是有序或逆序的时候，时间复杂度会增大

因为高度增大了，时间复杂度会变成O(n^2)

优化

但是，因为递归的原因，数量太大的时候，会造成栈溢出。所以我们要进行一定程度上的优化。

基准值的优化

为了防止出现只有基准值的一边有数据的情况，也就是基准值过大或过小，所以我们最好找到中间的基准值。

具体方法：

可以用最左边的值，最右边的值，中间的值，找到中间大小的值，并将该值和第一个值进行交换，使得该中间大小的值位于数组的第一个位置。

//三数取中
int midIndex=findMidIndex(array,left,right);
swap(array,left,midIndex);

public static int findMidIndex(int[] array,int left,int right){
    int midIndex=(left+right)/2;
    if(array[left]<=array[right]){
        if(array[midIndex]<=array[left])
            return left;
        else if(array[midIndex]>array[left]&&array[midIndex]<=array[right]){
            return midIndex;
        }
        else
            return right;
    }else{
        if(array[midIndex]<=array[right])
                return right;
        else if(array[midIndex]>array[right]&&array[midIndex]<=array[left]){
                return midIndex;
            }
        else
               return left;
    }
}

使用上面的三数取中法就可以有效的减少出现数据都在其中一边的情况，不再会出现栈溢出的问题。

和基准相同的数据

当数组中有和基准相同的数字的时候，可以将这些相同的数字移动到一块。因为如果移动到一块的时候，左右需要遍历的长度就会减少

聚集元素的过程比较复杂（了解就好）

下面给出一个博客，给出的过程比较明显

[博客链接]((384条消息) 快速排序的4种优化_Tyler_Zx的博客-CSDN博客_快速排序优化)

数据少的时候直接使用插入排序

因为直接插入排序具有数据量小，且相对有序的时候是高效的，所以再使用快排遍历一些小的部分的数据的时候，就可以使用直接插入排序来做。

if((right-left+1)<2){
    insertSort2(array,left,right);
}

public static void insertSort2(int[] array,int left,int right){
    for(int i=1;i<right;i++){
        int j=i-1;
        int tmp=array[i];
        for(;j>=left;j--){
            if(array[j]>tmp)
                array[j+1]=array[j];
            else
                //如果tmp比它大，就可以跳出循环了
                break;
        }
        array[j+1]=tmp;
    }
}

使用非递归

上面的快速排序我们使用了递归函数的方式——找完基准之后就递归左边，然后再递归右边。

但是，众所周知，递归的本质就是栈的调用问题。所以，所有的递归的问题都可以转化成栈的出入问题

下面我们就使用栈来替代递归

Stack<Integer> stack=new Stack<>();
int left=0;
int right=array.length-1;
int prvot=partition(array,left,right);
if(prvot>left+1) {
    stack.push(left);
    stack.push(prvot-1);
}
if(prvot<right-1){
    stack.push(prvot+1);
    stack.push(right);
}
while(!stack.isEmpty()){
    //注意：先出来的是右，后出来的是左
    right=stack.pop();
    left=stack.pop();

    prvot=partition(array,left,right);
    if(prvot>left+1) {
        stack.push(left);
        stack.push(prvot-1);
    }
    if(prvot<right-1){
        stack.push(prvot+1);
        stack.push(right);
    }
}

八、归并排序

归并排序是先分解，后合并。

先将一串数字分解成一个一个的数字后，再进行合并成一个小有序的数组，然后将这些有序的小的数组再合并成大的有序数组。

具体的解释请看下图：

首先先进行分：一半一半的分，直到被分成单个数字

然后进行治：合并两个有序数组

如此的进行递归，就可以完成递归排序得到一个有序的数组

代码实现：

public static void mergeSort(int[] array){
    merge(array,0,array.length-1);
}
public static void mergeOneArray(int[] array,int left,int mid,int right){
    //先创建一个数组，新的有序的数据保存再这个里面
    int[] tmp=new int[right-left+1];
    int s1=left,e1=mid;
    int s2=mid+1,e2=right;
    int i=0;//用于遍历tmp数组
    while(s1<=e1&&s2<=e2){
        if(array[s1]<=array[s2]){
            tmp[i++]=array[s1++];
        }else
            tmp[i++]=array[s2++];
    }
    while(s1<=e1)
        tmp[i++]=array[s1++];
    while(s2<=e2)
        tmp[i++]=array[s2++];
    //将新的tmp的值赋给array
    for (int j = 0; j < tmp.length; j++) {
 		//注意数组的起点是left+j
        array[left+j]=tmp[j];
    }
}
public static void merge(int[] array,int left,int right){
    //如果被分成了只有一个元素了，那就可以不‘分’了
    if(left>=right)
        return;
    int mid=left+((right-left)>>>1);
    //对左边和右边都进行'分‘
    merge(array,left,mid);
    merge(array,mid+1,right);
    //左右都进行完'分’了，就可以进行‘治’
    mergeOneArray(array,left,mid,right);
}

复杂度分析：

时间复杂度分析：

还是看上面的那个图，我们可以看到它呈现出二叉树的形式，分解的次数是logN次，也就是说有logN层，对于每一层，后面都会进行合并，合并的时间复杂度是整个数组的长度（对于每一层加起来都是这样）也就是O(N).所以，整个的时间复杂度度就是O(nlogN),和它一样的是堆排序，快排

空间复杂度分析：

因为每次合并的时候，都要新开辟一个数组，那个数组的长度就是O(N),所以空间复杂度就是O(N)

稳定性分析：

当if(array[s1]<=array[s2])的时候是稳定的：

如：6 7 和 5 6

稳定的排序只有三个：插入，冒泡，归并

非递归

同样的归并排序也可以使用非递归的方式来进行

根据上面的排序思想，就是将数字分成一个一个的数字之后，再合并成2个2个为一组的有序数组，然后再变成4个4个为一组的有序数组，直到数组的长度是整个的数组长度为止。所以还是利用上面的思想来进行非递归的排序

//非递归的排序
public static void mergeSort2(int[] array){
    int nums=1;//每个小数组的个数先从1开始
    //当每个数组的元素的个nums的个数还没有达到array.length的时候，就继续
    while(nums<array.length){
        //将整个数组都分成以nums*2个为长度的小数组
        for (int i = 0; i < array.length; i+=2*nums) {//注意i的下标的变化范围，要以nums为变化
            int left=i;
            int mid=left+nums-1;
            //防止溢出
            if(mid>=array.length) mid=array.length-1;
            int right=mid+nums;
            if(right>array.length) right=array.length-1;
            //进行合并
            mergeOneArray(array,left,mid,right);
        }
        nums*=2;//一步一步2倍nums的大小
    }
}

九、非比较排序

上面的都是一种比较排序，下面还有几种非比较排序，属于是用别的好方法了。十分的妙

基数排序

首先是先创建10个队列数组，然后看要比较的数字的个位数，按照个位数的值进入相对下标的数组中

如：

123就进入下标为3的数组中，10就进入下标为0的数组中。

等所有的数字全部都进入之后，就可以按照数组下标的顺序将队列中的元素全部排出，这样这些数组的个位数就有序了，

接着排十位数，百位数，直到没有为止

桶排序

将不同的元素加入到按照大小排序的不同范围的桶内部，然后将通内的元素进行排序。

之后按照通的顺序将桶中的元素排出即可

计数排序

//计数排序
public static void countingSort(int[] A,int K){
    int[] B=new int[A.length];
    int[] C=new int[K];
    //c[i]的值等于i出现的个数
    for (int i = 0; i < A.length; i++) {
        C[A[i]]++;
    }
    //c[i]是所以小于等于i的个数
    for (int i = 1; i <C.length ; i++) {
        C[i]=C[i]+C[i-1];
    }
    //从A的后到前，将排好序的元素保存在B中
    for (int i = A.length-1; i >=0 ; i--) {
        B[C[A[i]]]=A[i];
        C[A[i]]--;//里面的个数也减少
    }
}