快速排序

快速排序是一种著名的排序算法，1960年前后由英国科学家C. A. R. Hoare提出。其排序思想为：

• 从数列中挑出一个元素，称为基准(pivot)。
• 重新排序数列，所有比基准值小的元素放在基准前面，所有比基准值大的元素放在基准的后面。在分区结束后，该基准值就处于数列的中间位置，称为分区操作。
• 递归(Recursive)把小于基准值元素的子数列 和 大于基准值的子数列排序。

程序实现

• Python

def quick_sort(ls):
    def q_sort(ls,left,right):
        if left >= right:
            return
        i,j = left,right
        pivot = ls[left]
        while i<j:
            while ls[j] > pivot and i<j:
                j -= 1
            ls[i] = ls[j]
            while ls[i] <= pivot and i<j:
                i += 1
            ls[j] = ls[i]
        ls[i] = pivot
        q_sort(ls,left,i-1)
        q_sort(ls,i+1,right)
        return ls
    return q_sort(ls,0,len(ls)-1)

• C++

int partition(int nums[], int left, int right)  //找基准数 划分
{
     int i = left;
     int j = right;
     int temp = nums[left];
     while(i < j){
         while (i<j && nums[j] > temp){
             j--;
         }
         nums[i] = nums[j];
         while (i<j && nums[i] <= temp ){
             i++;
         }
         nums[j] = nums[i];
     }
     nums[i] = temp;
     return i;
 }

 void quick_sort(int nums[], int left, int right) {
     if (left >= right)
         return;
     int i = partition(nums, left, right);
     quick_sort(nums, left, i - 1);
     quick_sort(nums, i + 1, right);
 }

复杂度和稳定性

• 复杂度

抽象地看，快速排序产生的划分结构，可以看作以枢轴记录为根，以两个划分分段进一步划分的结果作为左右子树的二叉树。根据二叉树理论，所有n个结点的二叉树的平均高度为O(log n)。因此快速排序的平均时间为O(n log n)。

• 稳定性：不稳定。

当数列有两个或以上的元素时，快速排序会打破他们之间原有的顺序。