快速排序 python 代码实现

小咪咪 2024-02-19 20:33 19阅读 0赞

#### 原理: ####

快速排序（Quicksort）是对[冒泡排序][Link 1]的一种改进。

快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以[递归][Link 2]进行，以此达到整个数据变成有序[序列][Link 3]。

快速排序：是给基准数据找其正确索引位置的过程.  
   假设最开始的基准数为数组第一个元素,则首先用一个临时变量去存储基准数,即tmp;然后分别从数组的两端扫描数组，设两个指示标志:low指向起始位置，high指向末尾.

首先确定一个基准数：例如下图的基准数一般都是设置第一个数，基准数tmp=49 ，基准数在与剩下的n-1的部分进行，从最后一个数比较，若基准数小于进行交换，否者大于或者等于基准数不进行交换。此时将基准数与倒数第二个数进行比较27小于49，27和49进行交换。然后基准数49与第二数进行比较，若基准数=49大于第二个数38不交换，再与第三个数比较49<65 ,进行交换，以此类推，如下图

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDI5NDI1Ng_size_16_color_FFFFFF_t_70][]

动图：

![20190709160522150.gif][]

![20190709160442222.gif][]

#### 使用python 代码实现： ####

def quick_sort(data):
        """quick_sort"""
        if len(data) >= 2:
            mid = data[len(data)//2]
            left,right = [], []
            data.remove(mid)
            for num in data:
                if num >= mid:
                    right.append(num)
                else:
                    left.append(num)
            return quick_sort(left) + [mid] + quick_sort(right)
        else:
            return data

a = [2,3,4,1,45,6,6,7,8,7,9,10,18,20,30,12]

结果：

print(quick_sort(a))
    [1, 2, 3, 4, 6, 6, 7, 7, 8, 9, 10, 12, 18, 20, 30, 45]

#### **使用JAVA代码实现：** ####

public class QuickSort {
    //    //这是一个非常重要的排序方法（快速排序）
    
        public static int getMiddle(int array[],int left,int right){
            int key = array[left];
            while(left<right){
                while(array[right]>=key && left<right){
                    right--;
                }
                array[left] = array[right];
                while(array[left]<=key && left<right){
                    left++;
                }
                array[right]=array[left];
            }
            array[left] = key;
            return left;
        }
        public static void quickSort(int array[],int left,int right){
            if(left>right){
                return;
            }
            int middle = getMiddle(array, left,right);
            quickSort(array,left,middle-1);
            quickSort(array,middle+1,right);
        }
        public static void main(String[] args){
            int num[] ={2,3,4,1,45,6,6,7,8,7,9,10,18,20,30,12};
            quickSort(num,0,num.length-1);
            for(int n:num){
                System.out.print(" "+n);
            }
        }
    }

#### 小结： ####

#### 时间复杂度： ####

最好情况（待排序列接近无序）时间复杂度为O(nlog2n)

最坏情况（待排序列接近有序）时间复杂度为O(n2)

平均时间复杂度为O(nlog2n)。

[Link 1]: https://baike.baidu.com/item/%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F/4602306
[Link 2]: https://baike.baidu.com/item/%E9%80%92%E5%BD%92/1740695
[Link 3]: https://baike.baidu.com/item/%E5%BA%8F%E5%88%97/1302588
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDI5NDI1Ng_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/7b34ff4ca91345d59aa988e80758e713.png
[20190709160522150.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/66ca7a27465d4a5fb4659ac7e9f3ff9e.png
[20190709160442222.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/8ace61e8437c4044a4c9df0dc6278d3f.png