算法之快速排序

首先介绍一下quicksort：   
快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然 后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
                                                                                                               -------- 来自百度百科
    说白了，快速排序就是一种分区交换排序，冒泡排序的改进，采用分而治之的思想。快速排序首先将一个数分成两个较小的子序列：低元素和高元素。然后又分别快速对子序列递归调用，直至排序完成。
    一般步骤：
        1）选择一个元素pivot(枢轴、支点)，一般枢轴pivot取中间索引元素。（当然你也可以任意取）
        2）再定义两个变量left，right分别从数组的左右向pivot扫描，当left角标所在的值大于right角标所在的值时，交换数值，直到left>=right，一次快排就结束了，这就是所谓的分区操作。
        3）递归应用上述步骤，直至排序完成。

下面用java、c完成代码(只要理解了，什么语言写并不重要)
java代码如下：

/*=============================================================================
#     FileName: QuickSort.java
#         Desc: 快速排序（java）
#       Author: Icheon Tao
#        Email: [e-mail]
#     HomePage: http://blog.chinaunix.net/uid/30232980.html
#      Version: 0.0.1
#   LastChange: 2015-05-22 21:13:07
#      History:
=============================================================================*/

public class QuickSort {

    /**
     * @Synopsis  快速排序方法
     *
     * @Param data
     *
     * @Returns
     */
    public static void quickSort(int[] data) {
        quickSort(data,0,data.length-1);
    }

    /**
     * @Synopsis  quickSort(重载quickSort方法)
     * @Param data
     * @Param lowerIndex
     * @Param higherIndex
     * @Returns
     */
    public static int[] quickSort(int[] data,int lowerIndex,int higherIndex) {

        int left = lowerIndex;
        int right = higherIndex;
        int pivot = data[lowerIndex+(higherIndex-lowerIndex)/2]; // 这里用中间的当做枢轴pivot
        while (left <= right) { // 该循环将data数组分为两个数组进行排序
            while(data[right] > pivot) { // 从数组的右边依次往左遍历。直到找到比枢轴pivot小的数
                right--;
            }
            while(data[left] < pivot) { // 从数组的左边依次往右遍历。直到找到比枢轴pivot大的数
                left++;
            }
            if (left <= right) { // 如果找到了并且i<=j，就进行交换
                exchangeNumElement(data,left,right);
                left++;
                right--;
            }
        }
        if(lowerIndex < right) { // 分为两部分后继续递归调用quickSort
            quickSort(data,lowerIndex,right);
        }
        if(left < higherIndex) {
            quickSort(data,left,higherIndex);
        }
        return data;
    }

    /**
     * @Synopsis  用于交换数组的角标
     *
     * @Param a
     * @Param b
     *
     * @Returns
     */
    public static void exchangeNumElement(int[] data,int a,int b) {

        int temp = data[a];
        data[a] = data[b];
        data[b] = temp;
    }

    /**
     * @Synopsis  遍历输出数组
     *
     * @Param data
     *
     * @Returns
     */
    public static void printArray(int[] data) {
        for(int i = 0;i < data.length;i++) {
            System.out.print(data[i]+" ");
        }
    }

    /**
     * @Synopsis  main方法，程序入口
     *
     * @Param args
     *
     * @Returns
     */
    public static void main(String[] args) {

        int[] intArray = new int[10];
        for(int i = 0;i < intArray.length;i++) {
            intArray[i] = (int)(Math.random()*100+1);
        }
        quickSort(intArray);

        printArray(intArray);
    }
}

  c代码如下：

/*=============================================================================
#     FileName: QuickSort.c
#         Desc: 快速排序之c篇
#       Author: Icheon Tao
#        Email: [e-mail]
#     HomePage: http://blog.chinaunix.net/uid/30232980.html
#      Version: 0.0.1
#   LastChange: 2015-05-23 11:54:25
# History:
=============================================================================*/
#include<stdio.h>

/**
 * @Synopsis  交换数组中的两个元素的值
 *
 * @Param data
 * @Param a
 * @Param b
 */
void exchangeNumElement(int *data,int a,int b) {

    int temp = data[a];
    data[a] = data[b];
    data[b] = temp;
}
/**
 * @Synopsis  QuickSort函数
 *
 * @Param p
 * @Param lowerIndx
 * @Param higherIndex
 */
void quickSort (int *data,int lowerIndex,int higherIndex) {

    int left = lowerIndex;
    int right = higherIndex;
    int pivot = data[lowerIndex+(higherIndex-lowerIndex)/2];

    while (left <= right) { // 该循环将data数组分为两个数组进行排序
            while(data[right] > pivot) { // 从数组的右边依次往左遍历。直到找到比pivot小的数
                right--; //
            } //
            while(data[left] < pivot) { // 从数组的左边依次往右遍历。直到找到比pivot大的数
                left++; //
            } //
            if (left <= right) { // 如果找到了并且i<=j，就进行交换
                exchangeNumElement(data,left,right); //
                left++; //
                right--; //
            } //
        } //
        if(lowerIndex < right) { // 分为两部分后继续递归调用quickSort
            quickSort(data,lowerIndex,right);
        }
        if(left < higherIndex) {
            quickSort(data,left,higherIndex);
        }
    }


/**
 * @Synopsis  main函数-->程序入口
 *
 * @Returns
 */
int main() {
    int i = 0;
    int array[] = {4,9,2,5,6,1,7,3,8,0};
    int length = sizeof(array)/sizeof(array[0]);
    quickSort(array,0,length-1);
    for (i = 0;i < length;i++) {
        printf("%d ",array[i]);
    }
    return 0;
}

 
   
                                                                                            -------- 只想记录自己的自学之路