有趣的数据结构算法2——快速排序

题目复述

数据排序算法是一类常见算法，其适用范围深入编程的方方面面，常见的数据排序算法有冒泡排序、堆排序、简单选择排序等等，各个适用范围不同，快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

题目分析

对于快速排序而言，其通过一趟排序将要排序的数据分割成独立的两部分，即在所有数据中选出中间索引的数据，通过数据遍历将所有数据和这个数据进行比较，将大于该数据的归于同一边，小于该数据的归于另一边。然后再将分成功的左右两部分，重新各自执行上述操作，多次递归重复，即可完成排序。

接下来本文将通过实例分析对快速排序进行讲解
我们将要排序的序列是 { 78, 108, 111, 118, 101, 70, 105, 115, 104, 67, 46, 99, 111, 109 }。接下来是具体的排序方法：

此时便完成了一轮快速排序，此时左半部分都是大于105的数，右半部分都是小于105的数，将两个部分再次递归重复上述步骤，即可完成排序。

具体实现代码

 #include<stdio.h>
 void quick_sort(int array[], int low, int high){
 	int medium;
 	int i = low , j = high;
 	int temp;
 	medium = array[(i + j) / 2];
 	while (i <= j){	
 		while (array[i] < medium){
 			i++;
 		}
 		while (array[j] > medium){
 			j--;
 		}
 		if (i <= j){
 			temp = array[i];
 			array[i] = array[j];
 			array[j] = temp;
 			i++;
 			j--;
 		}
 	}
 	if (low < j){
 		quick_sort(array, low, j);
 	}
 	if (high > i){
 		quick_sort(array, i, high);
 	}
 }
 int main()
 {
 	int array[] = { 78, 108, 111, 118, 101, 70, 105, 115, 104, 67, 46, 99, 111, 109 };
 	int i, length;
 	length = sizeof(array) / sizeof(array[0]);
 	quick_sort(array,0,length - 1);
 	for (i = 0; i < length; i++){
 		printf("%d\n", array[i]);
 	}
 	return 0;
 }
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

GITHUB下载连接

https://github.com/bubbliiiing/Data-Structure-and-Algorithmr

希望得到朋友们的喜欢。
有问题的朋友可以提问噢。