0%

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)

Welcome to my other publishing channels