算法之快速排序算法的实现

分手后的思念是犯贱 2022-03-01 15:06 177阅读 0赞

快速排序这个算法的鼎鼎大名相信大家都有多耳闻，这个算法被称为20世纪对世界影响最大的之一，它之所以这么出名，可能就是因为像它名字一样，比较快吧。  
快速排序是从当前数组中选择一个数为基点，之后根据这个数的大小进行判断比这个数大还是比这个数小，下面我们用三种方法来解决这个快速排序算法。  
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。  
时间复杂度是O (nlogn)；

1.  基本排序  
    看图我们可以知道，最前边一个元素为v，索引定义为l，然后进行比较v和后边元素e的大小，如果比v大就放到arr\[J+1…i-1\]这个数组中，如果比v小就放到arr\[l+1…J\]这个数组中，这样的话中间值就作为J这个索引。然后进行递归处理两部分元素。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MTA1MTE1_size_16_color_FFFFFF_t_70]代码如下：

public class quickSort1 {
        public static void main(String[] args) {
            int n = 1000;
            //产生n个[0-n]范围的数组
            Comparable[] arr = SortTestHelper.generateRandomArray(n,0,n);
            long startTime = System.currentTimeMillis();
            quickSort(arr,arr.length);
            long endTime = System.currentTimeMillis();
            System.out.println("基本排序："+(endTime-startTime));
        }
    
        public static void quickSort(Comparable[] arr , int n){
            quickSort(arr, 0 , n-1);
        }
    
        // 对arr[l...r]部分进行partition操作
        // 返回p, 使得arr[l...p-1] < arr[p] ; arr[p+1...r] > arr[p]
        public static int partition(Comparable[] arr , int l,int r){
    
            //针对近乎有序的数组，如果不做这个解决就会出现n^2的复杂度
            swap(arr,l,(int)(Math.random()*(r-l+1)+l));
    
            Comparable v = arr[l];
            int j = l; // arr[l+1...j] < v ; arr[j+1...i) > v
            for( int i = l + 1 ; i <= r ; i ++ )
                if( arr[i].compareTo(v) < 0 ){
                    //j标记着中间的位置，如果arr[i]比v小的话，就把这个小值放到j前边，
                    // 跟j交换位置，如果比它大，就不需要变化
                    // 如果元素e和v相等的话就会出现O(n^2)的现象
                    j ++;
                    swap(arr, j, i);
                }
            //把v和j交换位置，这样v就到中间大的位置
            swap(arr, l, j);
    
            return j;
        }
    
        private static void swap(Object[] arr, int i, int j) {
            Object t = arr[i];
            arr[i] = arr[j];
            arr[j] = t;
        }
    
        public static void quickSort(Comparable[] arr, int l , int r){
            //如果值比较少的话就用插入排序，处理少量数据插入排序更快一些
            if ( r - l <= 15){
                insertSort(arr,l,r);
                return;
            }
            //进行快速排序逻辑运算，比v大就到右边，比v小就到左边，最后中间位置和v交换位置
            int p = partition(arr, l , r);
            quickSort(arr, 0 , p-1);
            quickSort(arr, p+1 , r);
        }
    
        public static void insertSort(Comparable[] arr,int l,int r){
            for (int i=l;i<r+1;i++){
                Integer e = Integer.parseInt(String.valueOf(arr[i]));
                int j;
                for (j = i;j>l;j--){
                    if (Integer.parseInt(String.valueOf(arr[j-1]))>Integer.parseInt(String.valueOf(e))){
                        arr[j] = arr[j-1];
                    }
                }
                arr[j] = e;
            }
        }
    }

1.  双路排序  
    如果基本排序处理大量的重复值的时候就会出现两部分的值差距很多，这样就会导致时间复杂度降低，我们就出现两个索引，一个i，一个J，i向右走，如果i的值大于v并且J的值小于v，则让i和J交换。最后让l和中间值J交换。  
    ![在这里插入图片描述][20190322212222217.png]代码如下

public class quickSort2 {
        public static void main(String[] args) {
            int n = 1000;
            Comparable[] arr = SortTestHelper.generateRandomArray(n,0,n);
            long startTime = System.currentTimeMillis();
            quickSort2(arr,arr.length);
            long endTime = System.currentTimeMillis();
            System.out.println("双路排序："+(endTime-startTime)+"ms");
        }
    
        public static void quickSort2(Comparable[] arr , int n){
            quickSort2(arr, 0 , n-1);
        }
    
        //返回p，使得arr[l..p-1]<arr[p] ; arr[p+1..r]>arr[p]
        public static int partition(Comparable[] arr, int l , int r){
            //针对近乎有序的数组，如果不做这个解决就会出现n^2的复杂度
            swap(arr,l,(int)(Math.random()*(r-l+1)+l));
            Comparable v = arr[l];
            int i=l+1,j=r;
            while (true){
                //i往后走，遇到比v小的就跳过
                while (arr[i].compareTo(v)<0 && i < r)
                    i++;
                //j往前走，遇到比v大的就跳过
                while (arr[j].compareTo(v)>0 && j > l+1)
                    j--;
                //如果遍历完就break掉
                if (i > j)
                    break;
                //这个就是当i的元素比v大，j的比v小进行交换
                swap(arr,i,j);
                i++;
                j--;
            }
            //把开始的值和中间值交换
            swap(arr,l,j);
            return j;
        }
    
    
        private static void swap(Object[] arr, int i, int j) {
            Object t = arr[i];
            arr[i] = arr[j];
            arr[j] = t;
        }
    
        public static void quickSort2(Comparable[] arr, int l , int r){
            //判断是否到中间那个位置
            if ( r - l <= 15){
                insertSort(arr,l,r);
                return;
            }
            //进行快速排序逻辑运算，比v大就到右边，比v小就到左边，最后中间位置和v交换位置
            int p = partition(arr, l , r);
            quickSort2(arr, 0 , p-1);
            quickSort2(arr, p+1 , r);
        }
    
        public static void insertSort(Comparable[] arr,int l,int r){
            for (int i=l;i<r+1;i++){
                Integer e = Integer.parseInt(String.valueOf(arr[i]));
                int j;
                for (j = i;j>l;j--){
                    if (Integer.parseInt(String.valueOf(arr[j-1]))>Integer.parseInt(String.valueOf(e))){
                        arr[j] = arr[j-1];
                    }
                }
                arr[j] = e;
            }
        }
    }

1.  三路排序  
    在排序中还有一个更经典的处理重复值较多的方法，那就是分为三部分，一部分是大于v的，一部分是大于v的，还有一部分就是等于v的，那么等于v的就不需要进行任何操作。  
    ![在这里插入图片描述][20190322213118450.png]代码如下：

public class quickSort3 {
        public static void main(String[] args) {
            int n = 1000;
            Comparable[] arr = SortTestHelper.generateRandomArray(n,0,n);
            long startTime = System.currentTimeMillis();
            quickSort3(arr,arr.length);
            long endTime = System.currentTimeMillis();
            System.out.println("三路排序："+(endTime-startTime));
        }
    
        public static void quickSort3(Comparable[] arr , int n){
            quickSort3(arr, 0 , n-1);
        }
    
    
        private static void swap(Object[] arr, int i, int j) {
            Object t = arr[i];
            arr[i] = arr[j];
            arr[j] = t;
        }
    
        //针对相同的数较多的
        //三路快速排序处理arr[l..r]
        //分为<v;=v;>v三部分进行排序
        //之后递归会<v;>v两部分进行排序
        public static void quickSort3(Comparable[] arr, int l , int r){
            //判断是否到中间那个位置
            if ( r - l <= 15){
                insertSort(arr,l,r);
                return;
            }
            //针对近乎有序的数组，如果不做这个解决就会出现n^2的复杂度
            swap(arr,l,(int)(Math.random()*(r-l+1)+l));
            Comparable v = arr[l];
            int lt = l; //arr[l+1..lt]<v
            int gt = r+1;//arr[gt..r]>v
            int i = l+1;//arr[lt+1..i]=v
            //当i<gt就是还没有碰上的时候
            while (i<gt){
                //当i位置的值小于v的时候
                if (arr[i].compareTo(v)<0){
                    //让i位置的值放到<v的区域中
                    swap(arr,i,lt+1);
                    lt++;
                    i++;
                } else if (arr[i].compareTo(v)>0){
                    swap(arr,i,gt-1);
                    gt--;
                    i++;
                } else {
                    i++;
                }
            }
            //把v和中间的元素交换
            swap(arr,l,lt-1);
            //进行快速排序逻辑运算，比v大就到右边，比v小就到左边，最后中间位置和v交换位置
            quickSort3(arr,l,lt-1);
            quickSort3(arr,gt,r);
        }
    
        public static void insertSort(Comparable[] arr,int l,int r){
            for (int i=l;i<r+1;i++){
                Integer e = Integer.parseInt(String.valueOf(arr[i]));
                int j;
                for (j = i;j>l;j--){
                    if (Integer.parseInt(String.valueOf(arr[j-1]))>Integer.parseInt(String.valueOf(e))){
                        arr[j] = arr[j-1];
                    }
                }
                arr[j] = e;
            }
        }
    }

大家可以在自己的电脑上运行一下这些代码测试一下，就可以比较出来这个运行时间的差距。祝大家学习算法成功。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MTA1MTE1_size_16_color_FFFFFF_t_70]: /images/20220301/daffc42228f842629e86dbb47a80f1ab.png
[20190322212222217.png]: /images/20220301/10d2210715f24217b91e0e7ed3419a86.png
[20190322213118450.png]: /images/20220301/8d2fbf18077f4709bbfea0ebb7251b21.png