Java实现快速排序

偏执的太偏执、 2021-12-24 06:01 263阅读 0赞

#### 快速排序思想 ####

**快速排序是一种交换排序**，所谓***交换排序就是利用交换元素位置进行排序的方法***。另一个交换排序是冒泡排序。

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：
    	任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，
    右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

#### 如下为一趟快速排序的流程图 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MDU3NDQz_size_16_color_FFFFFF_t_70]  
**经过一趟快速排序后，数组被分为三部分，比基准值小的，基准，比基准值大的，分别递归实现基准左边和基准右边的排序即可，思想是一样的。**

#### 快速排序为什么快？ ####

*  快速排序之所比较快，因为相比冒泡排序，每次交换是跳跃式的。
 *  每次排序的时候设置一个基准点，将小于等于基准点的数全部放到基准点的左边，将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样每次只能在相邻的数之间进行交换，交换的距离就大的多了。因此总的比较和交换次数就少了，速度自然就提高了。
 *  在最坏的情况下，仍可能是相邻的两个数进行了交换。因此快速排序的最差时间复杂度和冒泡排序是一样的都是O(N2)，它的平均时间复杂度为O(NlogN)。
 *  快速排序是基于一种叫做“二分”的思想。

#### 代码实现 ####

import java.util.Arrays;
    import java.util.*;
    
    public class QuickSort {
        
        public static void main(String[] args) {
        
            int[] array = new int[10000];
            Random random = new Random();
    
            for(int i=0; i<array.length; i++) {
        
                array[i] = random.nextInt(100000)+1;
            }
    
            quickSort(array);
    
            System.out.println(Arrays.toString(array));
        }
    
        public static void quick(int[] array, int start, int end) {
        
            int par = partion(array, start, end);
            if(par > start + 1) {
        
                quick(array, start, par-1);
            }
            if(par < end - 1) {
        
                quick(array, par + 1, end);
            }
        }
    
        public static void quickSort(int[] array) {
        
            quick(array,0,array.length-1);
        }
    
        public static int partion(int[] array, int low, int high) {
        
            int tmp = array[low];
            while(low < high) {
        
                while(low < high && array[high] >= tmp) {
        
                    high--;
                }
                if(low >= high) {
        
                    array[low] = tmp;
                    break;
                }else{
        
                    array[low] = array[high];
                }
    
                while(low < high && array[low] <= tmp) {
        
                    low++;
                }
                if(low >= high) {
        
                    array[low] = tmp;
                    break;
                }else{
        
                    array[high] = array[low];
                }
            }
            array[low] = tmp;
            return low;
        }
    }

#### 快速排序的复杂度 ####

**时间复杂度：O(NlogN)**  
**最优的情况下空间复杂度为：O(logn) ；每一次都平分数组的情况  
最差的情况下空间复杂度为：O( n ) ；退化为冒泡排序的情况**

#### 代码优化 ####

**选择基准的方式：三数取中法**

import java.util.Arrays;
    import java.util.*;
    
    public class QuickSort1 {
        
        public static void main(String[] args) {
        
            int[] array = new int[10];
            Random random = new Random();
    
            for(int i=0; i<array.length; i++) {
        
                array[i] = random.nextInt(10)+1;
            }
    
            quickSort(array);
    
            System.out.println(Arrays.toString(array));
        }
    
        public static void quick(int[] array, int start, int end) {
        
            
            medianOfThree(array, start, end);//三数取中法
    
            int par = partion(array, start, end);
    
            if(par > start + 1) {
        
                quick(array, start, par-1);
            }
            if(par < end - 1) {
        
                quick(array, par + 1, end);
            }
        }
    
        public static void quickSort(int[] array) {
        
            quick(array,0,array.length-1);
        }
    
        public static int partion(int[] array, int low, int high) {
        
            int tmp = array[low];
            while(low < high) {
        
                while(low < high && array[high] >= tmp) {
        
                    high--;
                }
                if(low >= high) {
        
                    array[low] = tmp;
                    break;
                }else{
        
                    array[low] = array[high];
                }
    
                while(low < high && array[low] <= tmp) {
        
                    low++;
                }
                if(low >= high) {
        
                    array[low] = tmp;
                    break;
                }else{
        
                    array[high] = array[low];
                }
            }
            array[low] = tmp;
            return low;
        }
    
        public static void swap(int[] array, int low, int high) {
        
            int tmp = array[low];
            array[low] = array[high];
            array[high] = tmp;
        }
    
        public static void medianOfThree(int[] array, int low, int high) {
        
            int mid = (low + high) / 2;
            //array[mid] <= array[low] <= array[high]
            if(array[mid] > array[low]) {
        
                swap(array, mid, low);
            }
            // if(array[mid] > array[high]) {
        
            //     swap(array, mid, high);
            // }
            if(array[low] > array[high]) {
        
                swap(array, low, high);
            }
        }
    }

**优化：已经有序部分不再递归**

import java.util.Arrays;
    import java.util.*;
    
    public class QuickSort2 {
        
        public static void main(String[] args) {
        
            int[] array = new int[1000];
            Random random = new Random();
    
            for(int i=0; i<array.length; i++) {
        
                array[i] = random.nextInt(1000)+1;
            }
    
            quickSort(array);
    
            System.out.println(Arrays.toString(array));
        }
    
        public static void insertSort2(int[] array, int start, int end) {
        
            for(int i = start + 1; i <= end; i++) {
        
                int tmp = array[i];
                int j = 0;
                for(j = i - 1; j >= start; j--) {
        
                    if(array[j] > tmp) {
        
                        array[j+1] = array[j];
                    }else {
        
                        break;
                    }
                }
                array[j+1] = tmp;
            }
        }
    
        public static void quick(int[] array, int start, int end) {
        
    
            if(end - start + 1 <= 16) {
        
                insertSort2(array, start, end);
                return;
            }
            
            medianOfThree(array, start, end);//三数取中法
    
            int par = partion(array, start, end);
    
            if(par > start + 1) {
        
                quick(array, start, par-1);
            }
            if(par < end - 1) {
        
                quick(array, par + 1, end);
            }
        }
    
        public static void quickSort(int[] array) {
        
            quick(array,0,array.length-1);
        }
    
        public static int partion(int[] array, int low, int high) {
        
            int tmp = array[low];
            while(low < high) {
        
                while(low < high && array[high] >= tmp) {
        
                    high--;
                }
                if(low >= high) {
        
                    array[low] = tmp;
                    break;
                }else{
        
                    array[low] = array[high];
                }
    
                while(low < high && array[low] <= tmp) {
        
                    low++;
                }
                if(low >= high) {
        
                    array[low] = tmp;
                    break;
                }else{
        
                    array[high] = array[low];
                }
            }
            array[low] = tmp;
            return low;
        }
    
        public static void swap(int[] array, int low, int high) {
        
            int tmp = array[low];
            array[low] = array[high];
            array[high] = tmp;
        }
    
        public static void medianOfThree(int[] array, int low, int high) {
        
            int mid = (low + high) / 2;
            //array[mid] <= array[low] <= array[high]
            if(array[mid] > array[low]) {
        
                swap(array, mid, low);
            }
            // if(array[mid] > array[high]) {
        
            //     swap(array, mid, high);
            // }
            if(array[low] > array[high]) {
        
                swap(array, low, high);
            }
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MDU3NDQz_size_16_color_FFFFFF_t_70]: /images/20211223/212ba83f88a247d39c23772747b3e5b8.png