用C语言实现快速排序算法

缺乏、安全感 2022-07-15 06:22 181阅读 0赞

一、快速排序算法（Quicksort）

1. 定义

快速排序由C. A. R. Hoare在1962年提出。快速排序是对冒泡排序的一种改进，采用了一种分治的策略。

![Center][]

2. 基本思想

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

3. 步骤

a. 先从数列中取出一个数作为基准数。

b. 分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。

c. 再对左右区间重复第二步，直到各区间只有一个数。

二、C语言实现代码（仅供参考）

**\[cpp\]** [ view plain][view plain] [ copy][view plain]

[print][view plain] [?][view plain] [![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

1.  /\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\* 
2.  File name：Quicksort 
3.  Author：Zhengqijun    Version:1.0    Date: 2016/11/04 
4.  Description: 对数组进行快速排序 
5.  Funcion List: 实现快速排序算法 
6.  \*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*/  
7.    
8.  \#include <stdio.h>  
9.  \#include <stdlib.h>  
10.   
11. \#define BUF\_SIZE 10  
12.   
13. /\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\* 
14.  \*函数名：display 
15.  \*作用：打印数组元素 
16.  \*参数：array - 打印的数组，maxlen - 数组元素个数 
17.  \*返回值：无 
18.  \*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*/  
19. void display(int array\[\], int maxlen)  
20. \{  
21.     int i;  
22.   
23.     for(i = 0; i < maxlen; i++)  
24.     \{  
25.         printf("%-3d", array\[i\]);  
26.     \}  
27.     printf("\\n");  
28.   
29.     return ;  
30. \}  
31.   
32. /\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\* 
33.  \*函数名：swap 
34.  \*作用：交换两个数的值 
35.  \*参数：交换的两个数 
36.  \*返回值：无 
37.  \*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*/  
38. void swap(int \*a, int \*b)    
39. \{  
40.     int temp;  
41.   
42.     temp = \*a;  
43.     \*a = \*b;  
44.     \*b = temp;  
45.   
46.     return ;  
47. \}  
48.   
49. /\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\* 
50.  \*函数名：quicksort 
51.  \*作用：快速排序算法 
52.  \*参数： 
53.  \*返回值：无 
54.  \*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*/  
55. void quicksort(int array\[\], int maxlen, int begin, int end)  
56. \{  
57.     int i, j;  
58.   
59.     if(begin < end)  
60.     \{  
61.         i = begin + 1;  // 将array\[begin\]作为基准数，因此从array\[begin+1\]开始与基准数比较！  
62.         j = end;        // array\[end\]是数组的最后一位  
63.             
64.         while(i < j)  
65.         \{  
66.             if(array\[i\] > array\[begin\])  // 如果比较的数组元素大于基准数，则交换位置。  
67.             \{  
68.                 swap(&array\[i\], &array\[j\]);  // 交换两个数  
69.                 j--;  
70.             \}  
71.             else  
72.             \{  
73.                 i++;  // 将数组向后移一位，继续与基准数比较。  
74.             \}  
75.         \}  
76.   
77.         /\* 跳出while循环后，i = j。 
78.          \* 此时数组被分割成两个部分  -->  array\[begin+1\] ~ array\[i-1\] < array\[begin\] 
79.          \*                           -->  array\[i+1\] ~ array\[end\] > array\[begin\] 
80.          \* 这个时候将数组array分成两个部分，再将array\[i\]与array\[begin\]进行比较，决定array\[i\]的位置。 
81.          \* 最后将array\[i\]与array\[begin\]交换，进行两个分割部分的排序！以此类推，直到最后i = j不满足条件就退出！ 
82.          \*/  
83.   
84.         if(array\[i\] >= array\[begin\])  // 这里必须要取等“>=”，否则数组元素由相同的值时，会出现错误！  
85.         \{  
86.             i--;  
87.         \}  
88.   
89.         swap(&array\[begin\], &array\[i\]);  // 交换array\[i\]与array\[begin\]  
90.           
91.         quicksort(array, maxlen, begin, i);  
92.         quicksort(array, maxlen, j, end);  
93.     \}  
94. \}  
95.   
96. // 主函数  
97. int main()  
98. \{  
99.     int n;  
100.     int array\[BUF\_SIZE\] = \{12,85,25,16,34,23,49,95,17,61\};  
101.     int maxlen = BUF\_SIZE;  
102.       
103.     printf("排序前的数组\\n");  
104.     display(array, maxlen);  
105.       
106.     quicksort(array, maxlen, 0, maxlen-1);  // 快速排序  
107.       
108.     printf("排序后的数组\\n");  
109.     display(array, maxlen);  
110.       
111.     return 0;  
112. \}

![save_snippets.png][]

/*****************************************************
    File name：Quicksort
    Author：Zhengqijun    Version:1.0    Date: 2016/11/04
    Description: 对数组进行快速排序
    Funcion List: 实现快速排序算法
    *****************************************************/
    
    #include <stdio.h>
    #include <stdlib.h>
    
    #define BUF_SIZE 10
    
    /**************************************************
     *函数名：display
     *作用：打印数组元素
     *参数：array - 打印的数组，maxlen - 数组元素个数
     *返回值：无
     **************************************************/
    void display(int array[], int maxlen)
    {
        int i;
    
        for(i = 0; i < maxlen; i++)
        {
            printf("%-3d", array[i]);
        }
        printf("\n");
    
        return ;
    }
    
    /********************************
     *函数名：swap
     *作用：交换两个数的值
     *参数：交换的两个数
     *返回值：无
     ********************************/
    void swap(int *a, int *b)  
    {
        int temp;
    
        temp = *a;
        *a = *b;
        *b = temp;
    
        return ;
    }
    
    /************************************
     *函数名：quicksort
     *作用：快速排序算法
     *参数：
     *返回值：无
     ************************************/
    void quicksort(int array[], int maxlen, int begin, int end)
    {
        int i, j;
    
        if(begin < end)
        {
            i = begin + 1;  // 将array[begin]作为基准数，因此从array[begin+1]开始与基准数比较！
            j = end;        // array[end]是数组的最后一位
              
            while(i < j)
            {
                if(array[i] > array[begin])  // 如果比较的数组元素大于基准数，则交换位置。
                {
                    swap(&array[i], &array[j]);  // 交换两个数
                    j--;
                }
                else
                {
                    i++;  // 将数组向后移一位，继续与基准数比较。
                }
            }
    
            /* 跳出while循环后，i = j。
             * 此时数组被分割成两个部分  -->  array[begin+1] ~ array[i-1] < array[begin]
             *                           -->  array[i+1] ~ array[end] > array[begin]
             * 这个时候将数组array分成两个部分，再将array[i]与array[begin]进行比较，决定array[i]的位置。
             * 最后将array[i]与array[begin]交换，进行两个分割部分的排序！以此类推，直到最后i = j不满足条件就退出！
             */
    
            if(array[i] >= array[begin])  // 这里必须要取等“>=”，否则数组元素由相同的值时，会出现错误！
            {
                i--;
            }
    
            swap(&array[begin], &array[i]);  // 交换array[i]与array[begin]
            
            quicksort(array, maxlen, begin, i);
            quicksort(array, maxlen, j, end);
        }
    }
    
    // 主函数
    int main()
    {
        int n;
        int array[BUF_SIZE] = {12,85,25,16,34,23,49,95,17,61};
        int maxlen = BUF_SIZE;
        
        printf("排序前的数组\n");
        display(array, maxlen);
        
        quicksort(array, maxlen, 0, maxlen-1);  // 快速排序
        
        printf("排序后的数组\n");
        display(array, maxlen);
        
        return 0;
    }

执行程序后的结果如下所示：

![Center 1][]

[Center]: /images/20220715/c672143ea16e45e785dec19433c35733.png
[view plain]: http://blog.csdn.net/zhengqijun_/article/details/53038831#
[CODE]: https://code.csdn.net/assets/CODE_ico.png
[CODE_CODE]: https://code.csdn.net/snippets/1967488
[ico_fork.svg]: https://code.csdn.net/assets/ico_fork.svg
[ico_fork.svg 1]: https://code.csdn.net/snippets/1967488/fork
[save_snippets.png]: /images/20220715/86cedd27c6a94134ac6b115df027cfe4.png
[Center 1]: /images/20220715/3feae0a3bb2347209dcdaef979074144.png