快速排序、快排的优化及Java实现

不念不忘少年蓝@ 2021-09-28 13:04 328阅读 0赞

# 一、快速排序的思想 #

选取一个比较的基准，将待排序数据分为独立的两个部分，左侧都是小于或等于基准，右侧都是大于或等于基准，然后分别对左侧部分和右侧部分重复前面的过程，也就是左侧部分又选择一个基准，又分为两个独立的部分，依次类推。到最后，整个序列就变得有序了

### 1、快速排序的方式(选取基准的方式)有三种： ###

①	 固定位置选取基准法
      ②	 随机选取基准法
      ③	三分取中法

**实现排序可以利用递归和非递归两种方式**

### 2、快排的优化： ###

①	当待排序序列中，需要排序的数字少许一定的个数时，采用直接插入排序
    ②	聚集相同基准元素法(待排序数据中有很多相同的数据)

### 3、复杂度、稳定性、优点 ###

*  **时间复杂度**：最好情况：O(nlog2n)  
    最坏情况：O(n2)
 *  **空间复杂度**：O(log2n)
 *  **稳定性**：不稳定
 *  **优点**：快速排序是对冒泡排序的增强，增强得点在于：冒泡排序中，数据的比较和移动是在相邻两个位置进行的，数据每次交换只能后移一个位置，因而总的比较次数和移动次数较多，而快排数据的比较和移动是从两端向中间进行的，较大的数一次就能从前面移动到后面，较小的数一次就能从后面移动到前面，这样就减少了比较次数和移动次数

### 4、图示 ###

##### ①固定位置选取基准法 #####

定义三个变量，low，high和tmp  
将l放入tmp，若前面有空位，从high后往前寻找比tmp小的值，放到前面空位；若后面有空位，从 l往后找比tmp大的值，放入后面的空位。直到l和h相遇，将tmp放入相遇的位置（此位置为基准）。此时发现tmp左边的值都比tmp小，右边的值都比tmp大。第一趟排序完成，再依次递归的排序基准左右两边的数据。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzg0MzUx_size_16_color_FFFFFF_t_70]  
**代码：**

//1.固定位置选取基准法
        int tmp = array[low];
        while(low < high) { 
            while (low < high && array[high] >= tmp) {   //high的值大于tmp，回退
                high--;
            }
            if (low >= high) { 
                break;
            } else { 
                array[low] = array[high];
            }
            while (low < high && array[low] <= tmp) {  //low的值小于tmp，判断下一个
                low++;
                if (low >= high) { 
                    break;
                } else { 
                    array[high] = array[low];
                }
            }
        }
        array[low] = tmp;
        return low;
    }

##### ②随 机选取基准法（预防待排序数据有序） #####

随机选取一个数字，和0号位置交换，再把这个数放入tmp，在后面找比它小的数，放到0号位置，h–，在前面找比它大的数，l++。

**代码：**

public static void swap(int[] array,int low,int high){   //交换low号下标和随机数下标的值
          int tmp = array[low];
          array[low] = array[high];
          array[high] = tmp;
        }
     public static void quick1(int[] array,int low,int high) { 
         Random random = new Random();
         int ranNum = random.nextInt(high-low+1)+low;
         swap(array,low,ranNum);
         int par = partion(array,low,high);
         if(par > low+1){   //左边有两个元素：起始low为0，par>1,在2号下标的位置，
             quick(array,low,par-1);
         }
         if(par < high-1){  //右边有两个元素：起始位par+1，
             quick(array,par+1,high);
         }
     }
    public static void quickSort1(int[] array){ 
        quick(array,0,array.length-1);
    }

##### ③三分取中法（预防待排序数据有序） #####

三个参数：low，high，和mid分别表示0号下标，最大号下标，最中间的下标，三者的值进行比较，把中间大的数字放在low，最大的放在high，最小的放在mid。  
**代码：**

public static void midThree(int[] array, int low, int high){ 
        //array[mid] <= array[low] <= array[high] 把中间大的数字放在第一个，最大的放在最后，最小的放在中间
        int mid = (high + low)/2;   //中间位置的下标
        if(array[low] > array[high]){ 
          swap(array,low,high);
        } //array[low] <= array[high]
        if(array[mid] > array[high]){ 
            swap(array,mid,high);
        }//array[mid] <= array[high]
        if(array[mid] > array[low]){ 
            swap(array,low,mid);
        }//array[mid] <= array[low]
    }

# 二、递归和非递归实现快速排序 #

### 1、递归实现：函数调用自己本身 ###

public static void quick(int[] array,int low,int high){   //low和high的值一直在发生改变,所以用递归找
        int par = partion(array,low,high);//par将数组分为两边
        if(par > low+1){   //左边有两个元素：起始low为0，par>1+0,在2号下标的位置，
            quick(array,low,par-1);
        }
        if(par < high-1){  //右边有两个元素：起始位par+1，
            quick(array,par+1,high);
        }
    }
    public static void quickSort(int[] array){ 
        quick(array,0,array.length-1);
    }

### 2、非递归实现 ###

需要栈来实现，现将low和high按顺序放入栈中，一次出栈两个值，出栈的第一个为high，第二个为low。  
注：在java中求log2N，首先要弄明白一个初中学到的公式  
log2N=logeN/loge2,  
logeN代表以e为底的N的对数,loge2代表以e为底的2的对数，在java.lang.math类中的log(double a)代表以e为底的a的对数,因此log2N在Java中的表示为：log((double)N)/log((double)2)

public static void quickSort2(int[] array) { 
        int len = (int) (log((double) array.length) / log((double) 2)); 
        int[] stack = new int[2 * len];//数组写的栈. 大小log2n
        int top = 0;
        int low = 0;
        int high = array.length - 1;
        int par = partion(array, low, high); //把数组分为两部分
        if (par > low + 1) { 
            //把左边和右边的low和high的值分别按先low后high的顺序压栈
            stack[top++] = low;
            stack[top++] = par - 1;
        }
        if(par < high -1) { 
            stack[top++] = par + 1;
            stack[top++] = high;
        }
        //一次出栈两个值，low和high。 把low放入tmp，判断和h的大小
        while (top > 0) { 
            high = stack[--top];
            low = stack[--top];
            par = partion(array, low, high);
    
            if (par > low + 1) { 
                stack[top++] = low;
                stack[top++] = par - 1;
            }
            if (par < high - 1) { 
                stack[top++] = par + 1;
                stack[top++] = high;
            }
        }

# 三、快排的优化 #

### 1、当某个区间需要排序的数据为一定范围时，进行直接插入排序 ###

public static void insertSort(int[] array, int low, int high){ 
        int tmp,j;
        for (int i = low+1; i <= high; i++) { 
            tmp = array[i];
            for (j = i-1; j >=low; j--) { 
                    if (array[j] > tmp) { 
                        array[j + 1] = array[j];
                    }  break;
                }
                array[j+1] = tmp;
            }
        }

### 2、聚集相同基准元素法 ###

待排序数据中有很多相同的数据时，要进行优化，则采取这个方式  
在基准（par）的左边和右边分别定义一个值，par\_left和par\_right,  
先判断基准右边：定义变量i，判断i下标的值是否和par对应的值相等，不相等的话，i++；相等的话par\_right和i先交换，然后par\_right和i的下标都+1.  
再用相同的方法判断基准的左边，

public static int[] Focus_Same_Num(int[] arr, int low, int par, int high, int left, int right) { 
        // 右边
        int par_right = par + 1;
        for (int i = par + 1; i <= high; i++) {  //右边
            if (arr[i] == arr[par]) {   //相同的话pr和i先交换再pr和i都++
                if (i != par_right) {  //不是紧挨着
                    swap(arr, i, par_right);
                    par_right++;
                } else {  //紧挨着，不用交换，比较下一个
                    par_right++;
                }
            }
        }
        right = par_right;
        //左 边
        int par_left = par - 1;
        for (int j = par - 1; j >= low; j--) {  //左边
            if (arr[j] == arr[par]) { 
                if (j != par_right) {  //不是紧挨着
                    swap(arr, j, par_left);
                    par_left--;
                } else {  //紧挨着，不用交换，比较下一个
                    par_left--;
                }
            }
        }
        left = par_left;
        int[] temp = new int[2];
        temp[0] = left;
        temp[1] = right;
        return temp;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzg0MzUx_size_16_color_FFFFFF_t_70]: /images/20210923/490a6a10f289481c8b6c7403e689207e.png