排序算法--------快速排序(分治法 )

我不是女神ヾ 2022-03-20 11:56 294阅读 0赞

### 快速排序 ###

*  1.简介
 *  2.实现的基本思想
 *  3.举个例子
 *  4.java代码实现
 *   *  4.1实现代码
     *  4.2 主方法代码
 *  5.快排总结
 *   *  5.1不足
     *  5.2改进策略

# 1.简介 #

快速排序的速度就如他的名字所示——快！并且这种算法一般被用作数量级比较大的数据当中，在大数据中有着很重要的地位。而快排主要有两部分，**分段(Partition)和递归(Recursive)**。分段既将一组数据相对一个参考值分为两段，左段比参考值小，右端比参考值大，然后再递归对这两段进行分段。把这两点把握好就可以写出一个快排算法了！！

# 2.实现的基本思想 #

1．先从数列中取出一个数作为基准数。

2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。

3．再对左右区间重复第一二步，直到各区间只有一个数。

# 3.举个例子 #

①创建一个数组

<table> 
 <thead> 
  <tr> 
   <th align="center">0</th> 
   <th align="center">1</th> 
   <th align="center">2</th> 
   <th align="center">3</th> 
   <th align="center">4</th> 
   <th align="center">5</th> 
   <th align="center">pivot</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center">46</td> 
   <td align="center">36</td> 
   <td align="center">55</td> 
   <td align="center">68</td> 
   <td align="center">11</td> 
   <td align="center">23</td> 
   <td align="center"></td> 
  </tr> 
 </tbody> 
</table>

②选择第一个元素46作为基准数。并从右边开始自右向左（下标记为end）寻找比基准元素小的元素填在第一个元素处

<table> 
 <thead> 
  <tr> 
   <th align="center">0</th> 
   <th align="center">1</th> 
   <th align="center">2</th> 
   <th align="center">3</th> 
   <th align="center">4</th> 
   <th align="center">5</th> 
   <th align="center">pivot</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center">23</td> 
   <td align="center">36</td> 
   <td align="center">55</td> 
   <td align="center">68</td> 
   <td align="center">11</td> 
   <td align="center"></td> 
   <td align="center">46</td> 
  </tr> 
 </tbody> 
</table>

③当右边替换一次时换为自左向右（下标记为start）寻找比基准元素大的元素填在空位处：

<table> 
 <thead> 
  <tr> 
   <th align="center">0</th> 
   <th align="center">1</th> 
   <th align="center">2</th> 
   <th align="center">3</th> 
   <th align="center">4</th> 
   <th align="center">5</th> 
   <th align="center">pivot</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center">23</td> 
   <td align="center">36</td> 
   <td align="center"></td> 
   <td align="center">68</td> 
   <td align="center">11</td> 
   <td align="center">55</td> 
   <td align="center">46</td> 
  </tr> 
 </tbody> 
</table>

④当左边替换一次时换为自右向左（下标记为end）寻找比基准元素小的元素填在空位处：

<table> 
 <thead> 
  <tr> 
   <th align="center">0</th> 
   <th align="center">1</th> 
   <th align="center">2</th> 
   <th align="center">3</th> 
   <th align="center">4</th> 
   <th align="center">5</th> 
   <th align="center">pivot</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center">23</td> 
   <td align="center">36</td> 
   <td align="center">11</td> 
   <td align="center">68</td> 
   <td align="center"></td> 
   <td align="center">55</td> 
   <td align="center">46</td> 
  </tr> 
 </tbody> 
</table>

⑤当右边替换一次时换为自左向右（下标记为start）寻找比基准元素大的元素填在空位处：

<table> 
 <thead> 
  <tr> 
   <th align="center">0</th> 
   <th align="center">1</th> 
   <th align="center">2</th> 
   <th align="center">3</th> 
   <th align="center">4</th> 
   <th align="center">5</th> 
   <th align="center">pivot</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center">23</td> 
   <td align="center">36</td> 
   <td align="center">11</td> 
   <td align="center"></td> 
   <td align="center">68</td> 
   <td align="center">55</td> 
   <td align="center">46</td> 
  </tr> 
 </tbody> 
</table>

⑥当start等于end时把基准数值填入空缺处

<table> 
 <thead> 
  <tr> 
   <th align="center">0</th> 
   <th align="center">1</th> 
   <th align="center">2</th> 
   <th align="center">3</th> 
   <th align="center">4</th> 
   <th align="center">5</th> 
   <th align="center">pivot</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center">23</td> 
   <td align="center">36</td> 
   <td align="center">11</td> 
   <td align="center">46</td> 
   <td align="center">68</td> 
   <td align="center">55</td> 
   <td align="center">46</td> 
  </tr> 
 </tbody> 
</table>

⑦递归上述步骤

# 4.java代码实现 #

## 4.1实现代码 ##

public static int partition(int[] arr,int strat,int end){ 
            //1.确定基准数
            int pivot =arr[strat];
            //2.确定结束条件
            while (strat < end)
            { 
                //3.从右向左找小于pivot的数来填arr[strat]
                while (strat < end && arr[end] > pivot){ 
                    end--;
                }
                if (strat < end) { 
                    arr[strat] = arr[end];
                    strat++;
                }
    
                //4.从左向右找大于或等于pivot的数来填arr[end]
                while (strat < end && arr[strat] <= pivot) { 
                    strat++;
                }
                if (strat < end) { 
                    arr[end] = arr[strat];
                    end--;
                }
            }
            //5.退出时，strat等于end。将pivot填到这个坑中
            arr[strat] = pivot;
            return strat;
        }
    
        public static void quick_sort(int[] arr, int strat, int end)
        { 
            int loc = 0;
            if (strat < end)
            { 
                //6.得到基准数的下标
                loc = partition(arr, strat, end);
                //7.递归调用
                quick_sort(arr, strat, loc - 1);
                quick_sort(arr, loc + 1, end);
            }
        }

## 4.2 主方法代码 ##

public static void main(String[] args) { 
            int[] x = {  46,36,55,68,11,23 };
            quick_sort(x, 0, x.length - 1);
            for (int i : x) { 
                System.out.print(i+" ");
            }
        }

# 5.快排总结 #

## 5.1不足 ##

**对于元素较少或接近有序的数组来说，快速排序平均性能比插入排序差**

*为什么？*

**因为小数组信息熵相对来说比较小（特别是经过一系列的快速排序调用以后），而插入排序在数据接近有序的情况下时间复杂度接近 O(N)，再加上快速排序递归调用也会有一些性能损耗。**

*如何解决？*

针对小数组，我们可以加个判断，**对小数组使用插入排序**。Java标准库自带的排序`DualPivotQuicksort`就是这么干的，`INSERTION_SORT_THRESHOLD` = 47。

## 5.2改进策略 ##

快排的改进主要有三种方法：`小数组使用插入排序`、`双枢轴（快速三向切分）`、`划分策略优化（五取样划分）`。经过优化后的快速排序算法时间复杂度可以介于 O(N) 到 O(NlogN) 之间，性能更优。有兴趣可以看 DualPivotQuicksort 的源码

***版权声明：本博客为记录本人自学感悟，转载需注明出处！  
[https://me.csdn.net/qq\_39657909][https_me.csdn.net_qq_39657909]***

[https_me.csdn.net_qq_39657909]: https://me.csdn.net/qq_39657909