开发笔记:快速排序详解（C语言/python）

1 #include
2 #include
3 //将arr数组中下标为i的与下标为j的交换位置
4 void Swap(int arr[], int i, int j)
5 {
6 int temp;
7 temp = arr[i];
8 arr[i] = arr[j];
9 arr[j] = temp;
10 }
11 //将arr数组进行划分
12 int Partition(int arr[], int left, int right)
13 {
14 //保存起始下标
15 int index = left;
16 //获取基准的值
17 int tmp = arr[left];
18 //循环查找 当left与right重合之后结束
19 while(left < right)
20 {
21 while(left = tmp)
22 {
23 right --;
24 }
25 //right从后面开始找 找到比tmp小的
26 while(left tmp)
27 {
28 left ++;
29 }
30 //left从前面开始找 找到比tmp大的
31 Swap(arr, left, right);
32 //将找出来的俩个交换位置
33 }
34 Swap(arr,index,left);
35 //将基准值换到left的位置上面，完成划分
36 return left;
37 }
38
39 void Qsort(int arr[], int left, int right)
40 {
41 int index;
42 if(left < right)
43 {
44 //划分arr数组 下标left到right部分
45 index = Partition(arr, left, right);
46 //划分完成之后递归对俩个独立分区进行快排
47 Qsort(arr, left, index - 1);
48 Qsort(arr, index + 1, right);
49 }
50 }
51 int main()
52 {
53 int arr[10]= {49,38,65,48,24,31,62,79};
54 int i;
55 Qsort(arr, 0, 7);
56 for(i=0; i<8; ++i)
57 {
58 printf("%d ",arr[i]);
59 }
60 return 0;
61 }

1 # coding=utf8
2 import uuid
3 import random
4 import string
5
6 def partition(alist, start, end):
7 index = start
8 tmp = alist[start]
9 while start < end:
10 while (start and alist[end] >= tmp):
11 end -= 1
12 while (start and alist[start] <= tmp):
13 start += 1
14 alist[start],alist[end] = alist[end],alist[start]
15 alist[index], alist[end] = alist[end], alist[index]
16 return end
17
18 def quick_sort(alist, start, end):
19 if start >= end:
20 return
21 left = partition(alist, start, end)
22 # 对左边部分执行快速排序
23 quick_sort(alist, start, left - 1)
24 # 对右边部分执行快速排序
25 quick_sort(alist, left + 1, end)
26
27 qlist = [49,38,65,48,24,31,62,79]
28 #qlist = [1, 12, 22, 34, 21, 4, 6, 8, 11, 54, 36, 7, 3, 0, 60, 62, 63]
29 quick_sort(qlist, 0, len(qlist) - 1)
30 print(qlist)

quick_sort = lambda array: array if len(array) <= 1 else quick_sort([item for item in array[1:] if item <= array[0]]) +[array[0]] + quick_sort([item for item in array[1:] if item >array[0]])