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

迈不过友情╰ 2021-12-12 15:19 254阅读 0赞

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

*  题目复述
 *  题目分析
 *  具体实现代码
 *  GITHUB下载连接

# 题目复述 #

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

# 题目分析 #

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

接下来本文将通过实例分析对快速排序进行讲解  
我们将要排序的序列是 \{ 78, 108, 111, 118, 101, 70, 105, 115, 104, 67, 46, 99, 111, 109 \}。接下来是具体的排序方法：  
![一轮快速排序示例][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc5MTk2NA_size_16_color_FFFFFF_t_70]  
此时便完成了一轮快速排序，此时左半部分都是大于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;
     }

# GITHUB下载连接 #

[https://github.com/bubbliiiing/Data-Structure-and-Algorithmr][https_github.com_bubbliiiing_Data-Structure-and-Algorithmr]

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

[20190723170158884.jpg_pic_center]: /images/20211210/1f5a4c0dc29949cf82edda93ee882fa9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc5MTk2NA_size_16_color_FFFFFF_t_70]: /images/20211210/e18a31bab56b436cae99604430818795.png
[https_github.com_bubbliiiing_Data-Structure-and-Algorithmr]: https://github.com/bubbliiiing/Data-Structure-and-Algorithmr