排序：Java实现快速排序原理及代码注释详解

╰半夏微凉° 2021-12-08 21:13 217阅读 0赞

## 快速排序 ##

**1.简介：**

> 快速排序是对冒泡排序的一种改进。它的最坏时间复杂度为O(n2)，最好时间复杂度为O(nlogn)，平均时间复杂度为O(nlogn)，它是不稳定排序。

基本思想：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

**2.算法原理：**

*  从数列中挑出一个元素，称为 “基准”；
 *  重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区操作；
 *  递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。

结合动态图理解一下：  
![在这里插入图片描述][20190715215152724.gif]  
（图片来源：[十大经典排序算法（动图演示）][Link 1]）  
**3.代码实现：**

public static void kuaiSu(int[] a,int low,int height){ 
            int i = low,j = height;
            if(low < height){ 
                int mark = a[low];
                while (i < j) { 
                    while (a[j] > mark && i < j){ 
                        j--;
                    }
                    if(i < j) { 
                        a[i] = a[j];
                        i++;
                    }
                    while (a[i] < mark && i < j){ 
                        i++;
                    }
                    if(i < j) { 
                        a[j] = a[i];
                        j--;
                    }
                }
                a[i] = mark;
                kuaiSu(a,low,i - 1);
                kuaiSu(a,i+1,height);
            }
        }

**测试一波：**

package sort;
    /** * @author yzh * @date 2019-07-15 20:36 */
    public class KuaiSu { 
        public static void kuaiSu(int[] a,int low,int height){ 
            int i = low,j = height;
            if(low < height){ 
                int mark = a[low];
                while (i < j) { 
                    while (a[j] > mark && i < j){ 
                        j--;
                    }
                    if(i < j) { 
                        a[i] = a[j];
                        i++;
                    }
                    while (a[i] < mark && i < j){ 
                        i++;
                    }
                    if(i < j) { 
                        a[j] = a[i];
                        j--;
                    }
                }
                a[i] = mark;
                kuaiSu(a,low,i - 1);
                kuaiSu(a,i+1,height);
            }
        }
        public static void main(String[] args) { 
            int[] a = { 4,-4,52,0,54,14,754};
            kuaiSu(a,0,a.length-1);
            for(int i = 0;i < a.length;i++){ 
                System.out.println(a[i]);
            }
        }
    }

**测试结果：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3NDgyMTkw_size_16_color_FFFFFF_t_70]  
**4.优缺点：**

*  优点：极快，数据移动少；
 *  缺点：不稳定。

[20190715215152724.gif]: /images/20211209/79b80ad38ed94a5f9e3e94d224dc25e5.png
[Link 1]: https://www.cnblogs.com/fivestudy/p/10212306.html
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3NDgyMTkw_size_16_color_FFFFFF_t_70]: /images/20211209/7b7a391c02c24b5db2abadf9435d9c78.png