算法导论学习002-快速排序

快速排序

简介

快速排序（英语：Quicksort），又称划分交换排序（partition-exchange sort），一种排序算法，最早由东尼·霍尔提出。
快速排序也属于比较排序中的一种，用到了分治的思想，综合来看快速排序是最常用的一种排序算法，速度快，效率高。

快速排序的描述

下面以对数组A[p...r]进行排序，来描述快速排序是如何利用分治思想进行快速排序的。

• 分解：数组A[p...r]被划分为两个(可能为空)的子数组A[p...q-1]和A[q+1,r]使得A[p..q-1]中每一个元素均小于或等于A[q] 而A[q+1...r]中每一个元素均大于等于A[q]. 划分的过程确定A[q]也是划分过程比较重要的部分，这里一般是选择最后一个元素为基准元素，然后遍历一遍数组，遍历过程中将每个元素与基准元素进行大小比较通过交换元素位置，最终在遍历完成时实现数组中基准元素左侧均小于它而它右侧的元素均大于它。(该过程可以结合看后面的伪代码以及代码实现能够更好的理解，基准元素也像一个哨兵的作用类似)
• 解决： 通过递归调用快速排序，对数组A[p...q-1]和A[q+1...r]进行排序 (该过程就是对划分的子数组再递归进行划分最终子数组为空或只有一个元素为止)
• 合并 因为子数组都是原址排序的，所以不需要合并操作 数组A[p...r]已经是有序的了(由于通过递归划分子数组，最终的每个子数组都是一个元素或为空，另外通过划分过程我们知道 相邻数组之间的元素是有序的比如左边数组的所有元素 均不大于右边数组里的元素 因此最终整个数组是有序的就完成了排序过程)

快速排序伪代码

QUICKSORT(A,p,r)

1. if(p<r)
2. q = PARTITION(A,p,r)
3. QUICKSORT(A,p,q-1)
4. QUICKSORT(A,q+1,r)

PARTITION(A,p,r)

1. x = A[r]
2. i = p-1
3. for(j = p to r-1)
4. if(A[j] <= x)
5. i++;
6. exchange(A[i],A[j])
7. exchange(A[i+1], A[r]
8. return i+1;

快速排序算法时间复杂度以及空间复杂度分析

• 空间复杂度
  由以上快排描述以及伪代码可知，除了定义了想x,i,j三个临时变量用来遍历调整交换原数组的元素位置以达到划分。因此空间复杂度很简单就是O(1).

• 时间复杂度
  由以上的伪代码可知快速排序 主要是遍历划分 和递归。先看看最差的情况假设选取的基准比较元素就是最小的那么每次划分的两个子数组 一个为空一个为剩余的元素 这样相当于要递归 遍历n次因此快速排序性能最差的情况下时间复杂度为O(n2), 最理想以及一般情况在递归划分时两个子数组划分均匀时 快排时间复杂度为O(nlgn)。在实际场景中 快速排序的时间复杂度接近O(nlgn).

End Talk Is Cheap Show You Mine Code

void quickSort(int *array, int start, int     end) {
if (arraySize == 0) {
    arraySize = end + 1;
}

if(start >= end){
    return;
}

logoutArray(array);
int i = partition(array,start,end);
quickSort(array,start, i-1);
quickSort(array,i+1,end);
}

int partition(int * array, int start , int     end){
int i , j ,tmp;
i = start;
j = end;

while(i != j){
    while(array[j] >= array[start] && i <     j){
        j--;
    }

    while(array[i] <= array[start] && i <     j){
        i++;
    }

    if(i < j){
        tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
}

tmp = array[start];
array[start] = array[i];
array[i] = tmp;

return i;
}