QuickSort in C & Python

本文主要关于演示C语言中的快排算法。

大名鼎鼎的QuickSort–快速排序算法，如此的高效、快速而优雅，今天让我们用图片和文字形象地展示一下它吧！

快排是一种分治算法，其主要思想在于通过选取一个基准Pivot将序列分为左右两个子序列，其中左序列的数都小于等于Pivot，右边的都大于等于Pivot，再在这两个子序列上递归调用快排算法即可。

而理解快排算法的核心就在于分解这个步骤，这里我们先给出代码，再用图片展示步骤。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
//
//  main.c
//  QuickSort
//
//  Created by frankchen on 12/2/16.
//  Copyright © 2016 frankchen. All rights reserved.
//


#include <stdio.h>

#define N 5


void QuickSort(int s[],int low,int high);
void swap(int s[],int i,int j);

int main(void){
    int a[N], i;
    
    printf("Enter %d numbers to be sorted: ", N);
    for (i=0; i<N; i++)
        scanf("%d", &a[i]);
    
    QuickSort(a, 0, N-1);
    
    printf("In sorted order: \n");
    for (i=0; i<N; i++)
        printf("%d ", a[i]);
    printf("\n");
    
    return 0;
}

//交换数组中的两个元素
void swap(int s[],int i,int j)
{
    int temp;
    temp=s[i];
    s[i]=s[j];
    s[j]=temp;
}

void QuickSort(int s[], int low, int high)
{
    int i, pivot;//记录界限的位置
    if(low < high)//只有数组中元素大于1时才操作
    {
        pivot = low;//选取第一个元素作为基准
        for(i=low+1; i<=high; i++)
        {
            if (s[i] < s[low])
                swap(s, ++pivot, i);
        }
        swap(s, low, pivot);//基准元与界限交换
        QuickSort(s, low, pivot-1);
        QuickSort(s, pivot+1, high);
    }
}

以下是Python版本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

class QuickSort(object):
    def __init__(self, l):
        '''
        初始化
        '''
        self.l = l
    
    def __str__(self):
        '''
        打印排序后的list
        '''
        return 'list\t:%s' % (self.l)
        
    def swap(self, s, i, j):
        '''
        交换位置
        '''
        tmp = 0
        tmp = s[i]
        s[i] = s[j]
        s[j] = tmp

    
    def QuickSort(self, s, low, high):
        i = 0; pivot = 0
        if low < high:
            pivot = low
            i = low + 1
            for i in range(i, high+1):
                if s[i] < s[low]:
                    pivot += 1
                    self.swap(s, pivot, i)
            self.swap(s, low, pivot)
            self.QuickSort(s, low, pivot-1)
            self.QuickSort(s, pivot+1, high)
        return s
    


def getList():
    '''
    读取文件内的数存入数组
    '''
    MyFile = "QuickSort.txt"
    l = []
    with open(MyFile) as f:
        for line in f.readlines():
            l.append(int(line))
    return l


def Sort():
    '''
    排序
    '''
    # 创建QuickSort对象
    l = getList()
    p = QuickSort(l)
    N = len(l)
    p.QuickSort(l, 0, N-1)
    return p


if __name__ == "__main__":
    p = Sort()
    print p
  • 为了排序整个序列，只需要调用QuickSort(R，0，n-1)即可完成对R[0..n-1]的排序。
  • 这里选取了第一个元素作为基准，如果输入是随机序列，那么没什么大碍，但是如果输入是预排序或者逆序的，那么会产生坏的排序，使得时间复杂度提高，随机选取基准是一种可行的方法，另外一种是选取开头、中间点和末位点的中位数。

![image](/images/2016/12/QuickSort/QuickSort.001.jpeg)
![image](/images/2016/12/QuickSort/QuickSort.002.jpeg)
![image](/images/2016/12/QuickSort/QuickSort.003.jpeg)
![image](/images/2016/12/QuickSort/QuickSort.004.jpeg)
![image](/images/2016/12/QuickSort/QuickSort.005.jpeg)
![image](/images/2016/12/QuickSort/QuickSort.006.jpeg)
![image](/images/2016/12/QuickSort/QuickSort.007.jpeg)
![image](/images/2016/12/QuickSort/QuickSort.008.jpeg)
![image](/images/2016/12/QuickSort/QuickSort.009.jpeg)
![image](/images/2016/12/QuickSort/QuickSort.010.jpeg)