一、快速排序算法（Quicksort）

1. 定义

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



2. 基本思想

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

3. 步骤

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

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

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

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

 

/*****************************************************
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 ;
}

/************************************
 *函数名：QuickSort
 *作用：快速排序算法
 *参数：
 *返回值：无
 ************************************/
void QuickSort(int *arr, int low, int high)
{
    if (low < high)
    {
        int i = low;
        int j = high;
        int k = arr[low];
        while (i < j)
        {
            while(i < j && arr[j] >= k)     // 从右向左找第一个小于k的数
            {
                j--;
            }

            if(i < j)
            {
                arr[i++] = arr[j];
            }

            while(i < j && arr[i] < k)      // 从左向右找第一个大于等于k的数
            {
                i++;
            }

            if(i < j)
            {
                arr[j--] = arr[i];
            }
        }

        arr[i] = k;

        // 递归调用
        QuickSort(arr, low, i - 1);     // 排序k左边
        QuickSort(arr, i + 1, high);    // 排序k右边
    }
}

// 主函数
int main()
{
    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, 0, maxlen-1);  // 快速排序
    
    printf("排序后的数组\n");
    display(array, maxlen);
    
    return 0;
}

 

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



上诉代码结合了我自己对快速排序的看法和理解，仅供参考。

 

快速排序是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。

其基本思想是：

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

/**

*    实验题目:

*        实现快速排序算法

*    实验目的:

*        领会快速排序过程和算法设计

*    实验内容:

*        设计程序，实现快速排序算法。用相关数据进行测试，并

*    输出各次划分后的结果。

*/

#include <stdio.h>

#define MAX_LEN     (100)                       //  最大长度

typedef int key_type;                           //  定义关键字类型为int

typedef char info_type;

typedef struct

{

    key_type key;                               //  关键字项

    info_type data;                             //  其他数据项,类型为info_type

}rec_type;                                      //  查找元素的类型

/*-----------------x和y交换------------------*/

void swap_rec(rec_type &x, rec_type &y)         //  引用类型

{

    rec_type tmp = x;

    x = y;

    y = tmp;

}

/*-----------------创建顺序表------------------*/

void create_list(rec_type recs[], key_type keys[], int n)

{

    int i;

    for(i = 0; i < n; i++)                      // recs[0...n-1]存放排序记录

        recs[i].key = keys[i];

}

/*-----------------输出顺序表------------------*/

void disp_list(rec_type recs[], int n)

{

    int i;

    for(i = 0; i < n; i++)

        printf("%d ", recs[i].key);

    printf("\n");

}

/*-----------------以下运算针对堆排序的程序------------------*/

/*-----------------创建顺序表------------------*/

void create_list1(rec_type recs[], key_type keys[], int n)

{

    int i;

    for(i = 1; i <= n; i++)                     // recs[1...n]存放排序记录

    {

        recs[i].key = keys[i - 1];

    }

}

/*-----------------输出顺序表------------------*/

void disp_list1(rec_type recs[], int n)

{

    int i;

    for(i = 1; i <= n; i++)

    {

        printf("%d ", recs[i].key);

    }

    printf("\n");

}

/*---------------显示一趟划分后的结果--------------*/

static void disp_partition(rec_type recs[], int s, int t)

{

    static int i = 1;                               // 局部静态变量仅被初始化一次

    int j;

    printf("第%d次划分:", i);

    for(j = 0; j < s; j++)

        printf("   ");

    for(j = s; j <= t; j++)

        printf("%3d", recs[j].key);

    printf("\n");

    i++;

}

/*---------------一趟划分--------------*/

static int partition_recs(rec_type recs[], int s, int t)

{

    int i = s, j = t;

    rec_type tmp = recs[i];                         //  以recs[i]为基准 [6, 8, 7, 9, 0, 1, 3, 2, 4, 5]

    while(i < j)                                    //  从两端交替向中间扫描,直至i=j为止

    {

        while(i < j && recs[j].key >= tmp.key)

            j--;                                    //  从右向左扫描,找一个小于tmp.key的recs[j]

        recs[i] = recs[j];                          //  找到这样的recs[j],放入recs[i]处

        while(i < j && recs[i].key <= tmp.key)

            i++;                                    //  从左向右扫描,找一个大于tmp.key的recs[i]

        recs[j] = recs[i];                          //  找到这样的recs[i],放入recs[j]处

    }

    recs[i] = tmp;

    disp_partition(recs, s, t);

    return i;

}

/*---------------对recs[s...t]的元素进行递增快速排序--------------*/

/**

*   快速排序基本思想:

*       通过一趟排序将要排序的数据分割成独立的两部分，

*   其中一部分的所有数据都比另外一部分的所有数据都要小，

*   然后再按此方法对这两部分数据分别进行快速排序，整个

*   排序过程可以递归进行，以此达到整个数据变成有序序列。

*/

static void quick_sort(rec_type recs[], int s, int t)

{

    int i;

    if(s < t)                                       //  区间内至少存在两个元素的情况

    {

        i = partition_recs(recs, s, t);

        quick_sort(recs, s, i - 1);                 //  对左区间递归排序

        quick_sort(recs, i + 1, t);                 //  对右区间递归排序

    }

}

int main(int argc, char *argv[])

{

    int n = 10;

    rec_type recs[MAX_LEN];

    key_type a[] = {6, 8, 7, 9, 0, 1, 3, 2, 4, 5};

    create_list(recs, a, n);

    printf("排序前: ");

    disp_list(recs, n);

    quick_sort(recs, 0, n - 1);// 0 9

    printf("排序后: ");

    disp_list(recs, n);

    return 0;

}

测试结果:

排序前: 6 8 7 9 0 1 3 2 4 5

第1次划分:  5  4  2  3  0  1  6  9  7  8

第2次划分:  1  4  2  3  0  5

第3次划分:  0  1  2  3  4

第4次划分:        2  3  4

第5次划分:           3  4

第6次划分:                       8  7  9

第7次划分:                       7  8

排序后: 0 1 2 3 4 5 6 7 8 9

快速排序(Quick sort)

快速排序（Quick sort），又称划分交换排序

快速排序算法如下:

	
从数列中挑出一个元素，称为"基准"（pivot），
		
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
		
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序
	
	
时间复杂度:
	
最优时间复杂度：O(nlogn)
		
最坏时间复杂度：O(n2)
			
稳定性：不稳定
		
		
代码实现如下:
	
#!/usr/bin/python
# coding=utf-8
def quick_sort(a_list, start, end):
    """快速排序"""
    if start >= end:
        return
    # 定义一个基准
    mid = a_list[start]
    left = start
    right = end

    # 如果left与right未重合, left就向中间(右)移动
    while left < right:
        while left < right and a_list[right] >= mid:
            right -= 1
        a_list[left] = a_list[right]
        while left < right and a_list[left] < mid:
            left += 1
        a_list[right] = a_list[left]
    # 从循环退出后, left与right相遇, 即 left==right
    a_list[left] = mid

    # 用递归对左边部分执行快速排序
    quick_sort(a_list, start, left-1)

    # 用递归对右边部分执行快速排序
    quick_sort(a_list, left+1, end)


if __name__ == '__main__':
    li = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    print(li)
    quick_sort(li, 0, len(li)-1)
    print(li)


# 输出结果:
排序前: [54, 26, 93, 17, 77, 31, 44, 55, 20]
排序后: [17, 20, 26, 31, 44, 54, 55, 77, 93]

快速排序算法的思想是：在数组中选取一个数（一般都是选第一个数），分别与其它的每一个数比较，把比这个数小的数放到它的前面，比他大的数放到它的后面，此时数组分成两部分，该数前面的都比它小，后面的都比它大，然后分别对这两部分递归排序算法，就可以实现整个数组的排序。
public static void main(String[] args) {
	
	    int [] arr = {65,58,95,10,57,62,13,106,78,23,85};
	    System.out.println("排序前："+Arrays.toString(arr));
	    quickSort(arr,0,arr.length-1);
	    System.out.println("排序后："+Arrays.toString(arr));
		
	}
	
	public static void quickSort(int [] arr,int left,int right) {
	      int pivot = 0;
	      if(left < right) {
	         pivot = partition(arr,left,right);
	         quickSort(arr,left,pivot-1);
	         quickSort(arr,pivot+1,right);
	      }
	   }
	
	private static int partition(int[] arr,int left,int right) {

	      int key = arr[left];
	      while(left < right) {
	         while(left < right && arr[right] >= key) {
	            right--;
	         }
	         arr[left] = arr[right];
	         while(left < right && arr[left] <= key) {
	            left++;
	         }
	         arr[right] = arr[left];
	      }
	      	 arr[left] = key;
	         return left;

	   }
	
解析如下：
                                    
此上过程是完成了一次排序，partition（）方法返回int类型的left，arr[left]将整个数组分成了两部分，左边的部分都比它小，右边的部分都比它大。然后运用递归的方法，分别对左边的数组部分和右边的部分重复上面的操作，最终可以实现数组的排序。



参考：http://blog.51cto.com/13733462/2113397