数据结构——排序_数据结构排序

Java排序

目录

Java排序

前言

一、简单排序 

1.冒泡排序

2.选择排序

3.插入排序

二、高级排序

1.希尔排序

2.归并排序

3.快速排序

三、排序的稳定性

前言

排序是非常常见的一种需求，提供一些数据元素，把这些数据元素按照一定的规则进行排序。以下会依次介绍排序算法。内容来自黑马程序员。

一、简单排序

1.冒泡排序

代码实现 ：

package 排序;
 
import javax.sound.midi.Soundbank;
import java.awt.image.ImageFilter;
import java.util.Arrays;
 
/**
 * @Date: 2022/1/6 - 01 - 06 - 14:04
 * @Description:
 */
public class Bubble {
    public static void sort(Comparable[] a){
        for (int i = a.length-1; i >0 ; i--) {
            for (int j = 0; j <i ; j++) {
                if (greater(a[j],a[j+1])){
                    exch(a,j,j+1);
                }
            }
        }
    }
    private static boolean greater(Comparable v,Comparable w){
        return v.compareTo(w)>0;
    }
    private static void exch(Comparable[] a,int i,int j){
        Comparable t=a[i];
        a[i]=a[j];
        a[j]=t;
    }
 
    public static void main(String[] args) {
        Integer[] a={4,5,2,3,7,8,0};
        Bubble.sort(a);
        System.out.println(Arrays.toString(a));
    }
}

2.选择排序

代码实现：

package 排序;
 
import java.util.Arrays;
 
/**
 * @Date: 2022/1/6 - 01 - 06 - 14:51
 * @Description:
 */
public class Selection {
    public static void sort(Comparable[] a){
        for (int i = 0; i <a.length-1; i++) {//因为剩余一个元素就不需要选择了，所以i <a.length-1
            //依次循环最小索引的值
            int min=i;
            for (int j = i+1; j <a.length ; j++) {
                if (greater(a[min],a[j])){//比较其与最小索引所在的值大小，如果最小索引处大，就交换下标值
                    min=j;
                }
            }
            exch(a,min,i);//交换下标之后将元素位置互换
        }
    }
    private static boolean greater(Comparable v,Comparable w){
        return v.compareTo(w)>0;
    }
    private static void exch(Comparable[] a,int i,int j){
        Comparable t=a[i];
        a[i]=a[j];
        a[j]=t;
    }
    public static void main(String[] args) {
        Integer[] a={4,5,2,3,7,8,0};
        Bubble.sort(a);
        System.out.println(Arrays.toString(a));
    }
}

 选择排序的时间复杂度分析：                                                                                                              选择排序使用了双层for循环，其中外层循环完成了数据交换，内层循环完成了数据比较，所以我们分别统计数据交换次数和数据比较次数：                                                                                        数据比较次数： (N-1)+(N-2)+(N-3)+...+2+1=((N-1)+1)*(N-1)/2=N^2/2-N/2;                                      数据交换次数：N-1                                                                                                                 时间复杂度：N^2/2-N/2+（N-1）=N^2/2+N/2-1; 根据大O推导法则，保留最高阶项，去除常数因子，时间复杂度为O(N^2);

3.插入排序

如图所示：

代码实现：

package 排序;
 
/**
 * @Date: 2022/1/6 - 01 - 06 - 15:30
 * @Description:
 */
public class Insertion {
    public static void sort(Comparable[] a){
        for(int i=1;i<a.length;i++){//从第二个元素开始遍历
            for(int j=i;j>0;j--){
                //比较索引j处的值和索引j-1处的值，如果索引j-1处的值比索引j处的值大，则交换数据，如果不大，那么就找到合适的位置了，退出循环即可；
                if (greater(a[j-1],a[j])){
                    exch(a,j-1,j);
                }else{
                    break;
                }
            }
        }
    }
    private static  boolean greater(Comparable v,Comparable w){
        return v.compareTo(w)>0;
    }
    private static void exch(Comparable[] a,int i,int j){
        Comparable temp;
        temp = a[i];
        a[i]=a[j];
        a[j]=temp;
    }
}

二、高级排序

1.希尔排序

代码实现：

package 排序;
 
/**
 * @Date: 2022/1/6 - 01 - 06 - 15:44
 * @Description:
 */
public class Shell {
    public static void sort(Comparable[] a){
        //1.根据数组a的长度，确定增长量h的初始值；
        int h = 1;
        while(h<a.length/2){
            h=2*h+1;
        }
        //2.希尔排序
        while(h>=1){
            //排序
            //2.1.找到待插入的元素
            for (int i=h;i<a.length;i++){
                //2.2把待插入的元素插入到有序数列中
                for (int j=i;j>=h;j-=h){
                    //待插入的元素是a[j],比较a[j]和a[j-h]
                    if (greater(a[j-h],a[j])){
                        //交换元素
                        exch(a,j-h,j);
                    }else{
                        //待插入元素已经找到了合适的位置，结束循环；
                        break;
                    }
                }
            }
            //减小h的值
            h= h/2;
        }
    }
    private static  boolean greater(Comparable v,Comparable w){
        return v.compareTo(w)>0;
    }
    private static void exch(Comparable[] a,int i,int j){
        Comparable temp;
        temp = a[i];
        a[i]=a[j];
        a[j]=temp;
    }
}

希尔排序和插入排序性能比较测试代码：

public class SortCompare {
    //调用不同的测试方法，完成测试
    public static void main(String[] args) throws Exception{
        //1.创建一个ArrayList集合，保存读取出来的整数
        ArrayList<Integer> list = new ArrayList<>();
 
        //2.创建缓存读取流BufferedReader，读取数据，并存储到ArrayList中；
        BufferedReader reader = new BufferedReader(new InputStreamReader(SortCompare.class.getClassLoader().getResourceAsStream("reverse_arr.txt")));
        String line=null;
        while((line=reader.readLine())!=null){
            //line是字符串，把line转换成Integer，存储到集合中
            int i = Integer.parseInt(line);
            list.add(i);
        }
 
        reader.close();
 
 
        //3.把ArrayList集合转换成数组
        Integer[] a = new Integer[list.size()];
        list.toArray(a);
        //4.调用测试代码完成测试
        //testInsertion(a);//37499毫秒
        testShell(a);//30毫秒
//        testMerge(a);//70毫秒
 
    }
 
    //测试希尔排序
    public static void testShell(Integer[] a){
        //1.获取执行之前的时间
        long start = System.currentTimeMillis();
        //2.执行算法代码
        Shell.sort(a);
        //3.获取执行之后的时间
        long end = System.currentTimeMillis();
        //4.算出程序执行的时间并输出
        System.out.println("希尔排序执行的时间为："+(end-start)+"毫秒");
 
    }
 
    //测试插入排序
    public static void testInsertion(Integer[] a){
        //1.获取执行之前的时间
        long start = System.currentTimeMillis();
        //2.执行算法代码
        Insertion.sort(a);
        //3.获取执行之后的时间
        long end = System.currentTimeMillis();
        //4.算出程序执行的时间并输出
        System.out.println("插入排序执行的时间为："+(end-start)+"毫秒");
    }
 
    //测试归并排序
    public static void testMerge(Integer[] a){
        //1.获取执行之前的时间
        long start = System.currentTimeMillis();
        //2.执行算法代码
        Merge.sort(a);
        //3.获取执行之后的时间
        long end = System.currentTimeMillis();
        //4.算出程序执行的时间并输出
        System.out.println("归并排序执行的时间为："+(end-start)+"毫秒");
    }
 
}

2.归并排序

排序原理：

        1.尽可能的一组数据拆分成两个元素相等的子组，并对每一个子组继续拆分，直到拆分后的每个子组的元素个数是1为止。

        2.将相邻的两个子组进行合并成一个有序的大组；

        3.不断的重复步骤 2 ，直到最终只有一个组为止。

如图所示：

填充原理：将原数组分为左子组和右子组，p1指针为左子组指针，p2为右子组指针，并设置i为辅助数组指针。比较当前p1,p2指针所指的元素大小，将小的放到指针i处；然后向后移动p1,p2,i指针继续比较。

 

 

 

代码实现：

package 排序;
 
/**
 * @Date: 2022/1/7 - 01 - 07 - 10:14
 * @Description:
 */
public class Merge {
    //归并所需要的辅助数组
    private static Comparable[] assist;
    private static boolean less(Comparable v, Comparable w) {
        return v.compareTo(w)<0;
    }
    private static void exch(Comparable[] a, int i, int j) {
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
    public static void sort(Comparable[] a) {
        //1.初始化辅助数组assist；
        assist = new Comparable[a.length];
        //2.定义一个lo变量，和hi变量，分别记录数组中最小的索引和最大的索引；
        int lo=0;
        int hi=a.length-1;
        //3.调用sort重载方法完成数组a中，从索引lo到索引hi的元素的排序
        sort(a,lo,hi);
    }
    private static void sort(Comparable[] a, int lo, int hi) {
        //做安全性校验；
        if (hi<=lo){
            return;
        }
        //对lo到hi之间的数据进行分为两个组
        int mid = lo+(hi-lo)/2;//   5,9  mid=7
        //分别对每一组数据进行排序
        sort(a,lo,mid);
        sort(a,mid+1,hi);
        //再把两个组中的数据进行归并
        merge(a,lo,mid,hi);
    }
    private static void merge(Comparable[] a, int lo, int mid, int hi) {
        //定义三个指针
        int i=lo;
        int p1=lo;
        int p2=mid+1;
        //遍历，移动p1指针和p2指针，比较对应索引处的值，找出小的那个，放到辅助数组的对应索引处
        while(p1<=mid && p2<=hi){
            //比较对应索引处的值
            if (less(a[p1],a[p2])){
                assist[i++] = a[p1++];
            }else{
                assist[i++]=a[p2++];
            }
        }
        //遍历，如果p1的指针没有走完，那么顺序移动p1指针，把对应的元素放到辅助数组的对应索引处
        while(p1<=mid){
            assist[i++]=a[p1++];
        }
        //遍历，如果p2的指针没有走完，那么顺序移动p2指针，把对应的元素放到辅助数组的对应索引处
        while(p2<=hi){
            assist[i++]=a[p2++];
        }
        //把辅助数组中的元素拷贝到原数组中
        for(int index=lo;index<=hi;index++){
            a[index]=assist[index];
        }
    }
}

归并排序时间复杂度分析：

        归并排序是分治思想的最典型的例子，上面的算法中，对a[lo...hi] 进行排序，先将它分为 a[lo...mid] 和 a[mid+1...hi]两部分，分别通过递归调用将他们单独排序，最后将有序的子数组归并为最终的排序结果。该递归的出口在于如果一个数组不能再被分为两个子数组，那么就会执行merge 进行归并，在归并的时候判断元素的大小进行排序。用树状图来描述归并，如果一个数组有8 个元素，那么它将每次除以 2 找最小的子数组，共拆 log8 次，值为 3 ，所以树共有3 层 , 那么自顶向下第 k 层有 2^k 个子数组，每个数组的长度为 2^(3-k) ，归并最多需要 2^(3-k) 次比较。因此每层的比较次数为 2^k * 2^(3-k)=2^3, 那么 3 层总共为 3*2^3。 假设元素的个数为n ，那么使用归并排序拆分的次数为 log2(n), 所以共 log2(n) 层，那么使用 log2(n) 替换上面 3*2^3 中的3 这个层数，最终得出的归并排序的时间复杂度为： log2(n)* 2^(log2(n))=log2(n)*n, 根据大 O 推导法则，忽略底数，最终归并排序的时间复杂度为O(nlogn)

代码测试如上希尔排序。

3.快速排序

排序原理：

        1.首先设定一个分界值，通过该分界值将数组分成左右两部分；

        2.将大于或等于分界值的数据放到到数组右边，小于分界值的数据放到数组的左边。此时左边部分中各元素都小于 或等于分界值，而右边部分中各元素都大于或等于分界值；

        3.然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两 部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。

        4.重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左侧和右侧两个部分的数据排完序后，整个数组的排序也就完成了

如图所示：

切分原理：

把一个数组切分成两个子数组的基本思想：

1. 找一个基准值，用两个指针分别指向数组的头部和尾部；

2. 先从尾部向头部开始搜索一个比基准值小的元素，搜索到即停止，并记录指针的位置；

3. 再从头部向尾部开始搜索一个比基准值大的元素，搜索到即停止，并记录指针的位置；

4. 交换当前左边指针位置和右边指针位置的元素；

5. 重复 2,3,4 步骤，直到左边指针的值大于右边指针的值停止。

代码实现： 

package 排序;
 
/**
 * @Date: 2022/1/7 - 01 - 07 - 10:36
 * @Description:
 */
public class Quick {
    private static boolean less(Comparable v, Comparable w) {
        return v.compareTo(w) < 0;
    }
    private static void exch(Comparable[] a, int i, int j) {
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
    public static void sort(Comparable[] a) {
        int lo = 0;
        int hi = a.length-1;
        sort(a,lo,hi);
    }
    private static void sort(Comparable[] a, int lo, int hi) {
        //安全性校验
        if (hi<=lo){
            return;
        }
        //需要对数组中lo索引到hi索引处的元素进行分组（左子组和右子组）；
        int partition = partition(a, lo, hi);//返回的是分组的分界值所在的索引，分界值位置变换后的索引
        //让左子组有序
        sort(a,lo,partition-1);
        //让右子组有序
        sort(a,partition+1,hi);
    }
    //对数组a中，从索引 lo到索引 hi之间的元素进行分组，并返回分组界限对应的索引
    public static int partition(Comparable[] a, int lo, int hi) {
        //确定分界值,就是第一个元素
        Comparable key = a[lo];
        //定义两个指针，分别指向待切分元素的最小索引处和最大索引处的下一个位置
        int left=lo;
        int right=hi+1;
        //切分
        while(true){
            //先从右往左扫描，移动right指针，找到一个比分界值小的元素，停止
            while(less(key,a[--right])){
                if (right==lo){
                    break;
                }
            }
            //再从左往右扫描，移动left指针，找到一个比分界值大的元素，停止
            while(less(a[++left],key)){
                if (left==hi){
                    break;
                }
            }
            //判断 left>=right,如果是，则证明元素扫描完毕，结束循环，如果不是，则交换元素即可
            if (left>=right){
                break;
            }else{
                exch(a,left,right);
            }
        }
        //交换分界值，此时right=left所指的位置
        exch(a,lo,right);
        //最终返回分界值即可
        return right;
    }
 
}

快速排序和归并排序的区别：

        快速排序是另外一种分治的排序算法，它将一个数组分成两个子数组，将两部分独立的排序。快速排序和归并排序是互补的：归并排序将数组分成两个子数组分别排序，并将有序的子数组归并从而将整个数组排序，而快速排序的方式则是当两个数组都有序时，整个数组自然就有序了。在归并排序中，一个数组被等分为两半，归并调用发生在处理整个数组之前，在快速排序中，切分数组的位置取决于数组的内容，递归调用发生在处理整个数组之后。

快速排序时间复杂度分析：

        快速排序的一次切分从两头开始交替搜索，直到left 和 right 重合，因此，一次切分算法的时间复杂度为 O(n), 但整个快速排序的时间复杂度和切分的次数相关。

        最优情况：每一次切分选择的基准数字刚好将当前序列等分。

如果我们把数组的切分看做是一个树，那么上图就是它的最优情况的图示，共切分了 logn 次，所以，最优情况下快速排序的时间复杂度为O(nlogn);

        最坏情况：每一次切分选择的基准数字是当前序列中最大数或者最小数，这使得每次切分都会有一个子组，那么总共就得切分 n 次，所以，最坏情况下，快速排序的时间复杂度为O(n^2);

        平均情况：每一次切分选择的基准数字不是最大值和最小值，也不是中值，这种情况我们也可以用数学归纳法证明，快速排序的时间复杂度为O(nlogn),由于数学归纳法有很多数学相关的知识，容易使我们混乱，所以这里就不对平均情况的时间复杂度做证明了。

三、排序的稳定性

• 冒泡排序： 只有当arr[i]>arr[i+1]的时候，才会交换元素的位置，而相等的时候并不交换位置，所以冒泡排序是一种稳定排序 算法。
• 选择排序: 选择排序是给每个位置选择当前元素最小的,例如有数据{5(1)，8 ，5(2)， 2， 9 },第一遍选择到的最小元素为2，所以5(1)会和2进行交换位置，此时5(1)到了5(2)后面，破坏了稳定性，所以选择排序是一种不稳定的排序算法。
• 插入排序：比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的，那么把要插入的元素放在相等 元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。
• 希尔排序：希尔排序是按照不同步长对元素进行插入排序 ,虽然一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以希尔排序是不稳定的。
• 归并排序：归并排序在归并的过程中，只有arr[i]<arr[i+1]的时候才会交换位置，如果两个元素相等则不会交换位置，所以它并不会破坏稳定性，归并排序是稳定的。
• 快速排序：快速排序需要一个基准值，在基准值的右侧找一个比基准值小的元素，在基准值的左侧找一个比基准值大的元素，然后交换这两个元素，此时会破坏稳定性，所以快速排序是一种不稳定的算法。