基础算法之快速排序

插入排序是一种最基本的排序方法，时间复杂度为O(nlogn)。效率较高，而且在笔试面试中经常会被问到，要多写多练做到可以随时随手写出快排的目标。

快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。

该方法的基本思想是：

1．先从数列中取出一个数作为基准数。（此处我们每次选取的是数组的第一个元素）

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

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

贴一个通俗易懂的链接：http://blog.csdn.net/morewindows/article/details/6684558

用C语言简单实现的插入排序如下：

 1 /* 快速排序算法的C语言实现 */
 2 /* s为要进行排序的数组，l是要排序数组的起始位置， */
 3 
 4 void quick_sort(int s[], int l, int r)
 5 {
 6     if(l<r) {
 7         int i = l, j = r, x = s[l];
 8         while(i<j)
 9         {
10             while(i<j&&s[j]>=x) {
11                 j--;
12             }
13             if(i<j) {
14                 s[i++] = s[j];
15             }
16             while(i<j&&s[i]<=x) {
17                 i++;
18             }
19             if(i<j) {
20                 s[j--] = s[i];
21             }
22         }
23         s[i] = x;
24         quick_sort(s, l, i-1);
25         quick_sort(s, i+1, r);
26     }
27 }

一个简单的测试用例，代码如下：

#include<stdio.h>

#define MAXSIZE 10

/* 快速排序算法的C语言实现 */
/* s为要进行排序的数组，l是要排序数组的起始位置， */

void quick_sort(int s[], int l, int r)
{
    if(l<r) {
        int i = l, j = r, x = s[l];
        while(i<j)
        {
            while(i<j&&s[j]>=x) {
                j--;
            }
            if(i<j) {
                s[i++] = s[j];
            }
            while(i<j&&s[i]<=x) {
                i++;
            }
            if(i<j) {
                s[j--] = s[i];
            }
        }
        s[i] = x;
        quick_sort(s, l, i-1);
        quick_sort(s, i+1, r);
    }
}


int main()
{
    int a[MAXSIZE];
    int i;
    printf("Please input the num:
");
    for(i=0; i<MAXSIZE; i++)
    {
        scanf("%d",&a[i]);
    }
    printf("before the sort:
");
    for(i=0; i<MAXSIZE; i++)
    {
        printf("%d ", a[i]);
    }
    printf("
");
    
    quick_sort(a, 0, MAXSIZE);

    printf("after the sort:
");
    for(i=0; i<MAXSIZE; i++)
    {
        printf("%d ", a[i]);
    }
    printf("
");
}

View Code