分治法实例（快排）_大数据分治法实例

分治法思想

分治法的精髓：

1. 分–将问题分解为规模更小的子问题；
2. 治–将这些规模更小的子问题逐个击破；
3. 合–将已解决的子问题合并，最终得出“母”问题的解；

快排

快速排序原理：从一组数中选出一个pivot(中心轴)，将大于它的数放右边，小于它的数放左边，然后再从左边和右边的俩组数中分别执行此操作，此时，数组就是有序的了。

//
// Created by a1073 on 2019/7/4.
//

#include <stdio.h>

void quickSort(int[], int, int);

int main(void) {
    int array[6] = {1, 9, 4, 6, 3, 2};
    quickSort(array, 0, 5);
    for (int i = 0; i < 6; ++i) {
        printf("array[%d] = %d\n", i, array[i]);
    }
    return 0;
}

void quickSort(int array[], int left, int right) {
    int i = left;
    int j = right;
    int temp;
    int pivot; //中心轴

    pivot = array[(i + j) / 2];

    while (i <= j) {
        while (array[i] < pivot) {
            /*
             * 向右搜索比pivot值大数据*/
            i++;
        }
        while (array[j] > pivot) {
            /*
             * 向左搜索比pivot值小的数据*/
            j--;
        }
        if (i <= j) {
            /*
             * if的判断条件与while的循环条件不重复
             * while的判断条件仅仅是控制循环次数
             * 而if中的判断——是否执行互换的条件
             * 如果i>j的话代表此次的循环结束*/

            temp = array[i];
            array[i] = array[j];
            array[j] = temp;
            i++;
            j--;
        }
    }
    /*
     * 此刻i在j的右边
     * 必须进行判断才能进行递归
     * 否则在到最后无法停止递归
     * */
    if(j > left){
        quickSort(array, left, j);
    }

    if(i < right){
        quickSort(array, i, right);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

千万注意最后的结束条件！！！