第一章

桶排序（简版）

这是一种对于n个数据排序的方式

这个算法是假设了有n个桶，编号便是0-*(n-1)，共n个桶来装数据
每当出现了一个数，我们就在对应编号的桶中放置一个标志
查看数据时只要看每个桶中有多少数据即可

//比如我们对0-10的数进行排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int a[11] ;
int i,j,t ; 

for(i = 10 ; i >= 0 ; i++){
    a[i] = 0 ; //讲每个桶的原始值设为0
}

for(i =1 ; i <=5 ; i++){
    //循环读入数据，我们这里就设读入五个吧
    scanf("%d" , &t);
    a[t]++ ; //相关计数
}

for(i = 10 ; i >= 0 ; i++){
    //依次判断a[0]到a[10]
    for(j =1 ; j<=a[i];j++){
        printf("d",i) ; //打印，出现几次打印几次
    }
}

在这个简化版的桶排序中，有一个缺陷：我们并不知道排序后的数据原本对应哪个数据源
而且，桶排序还非常浪费空间。当我们排序的范围扩大而数据总量不变之后，明显会有很多无用”空桶”(比如我们记录1-1000的数值，但是出现的数字只有1和2)
简言之，桶排序只适合进行简单的排序分类，对于更复杂、更高要求的排序，我们还需要更好的方法

冒泡排序

核心思想在于“每次比较两个相邻的元素，如果它们顺序错误就把它们交换过来”，那什么是所谓顺序错误呢？
比如，我们想要进行从大到小的排序，则把小的数字往后靠

比如有五个数字12 35 99 18 76 ，我们试图将它们从大到小排序
1.我们首先比较第一12和第二35，显然35大。依据核心思想，替换二者。那么现在五个数的顺序就是： 35 12 99 18 76
2.接着我们去比较现在的第二位12和第三位99，显然12又是更小的那个数，现在顺序变为35 99 12 18 76
3.重复上面的步骤直到比较完最后一位数字，最后我们得到的顺序是35 99 18 76 12，我们可以发现，“一趟”下来之后，我们将最小的数字排序到了最后面，看到这”冒泡”的说法已经被体现出来了。
4.重复上述步骤，依次找到“第二小的”，“第三小的”…最终完成我们的排序。冒泡排序，每一趟只可以确定将一个数归位

总结：有n个数字进行排序，只需要将n-1个数归位，进行n-1趟操作

代码示例

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
int a[100] ; 
int i,j,t,n ; 
//输入一个数n，表示下面有n个数字
scanf("%d",&n);

for(i = 1 ; i <= n ; i++){
    //循环读入n个数到我们的数组a中
    scanf("%d",&a[i]);
    //实际上，n是要小于101的(因为前面把数组大小定为了100)
}

//！下面就是冒泡排序的核心算法了
for(i = 1 ; i <= n-1 ; i++){
    for(j =1 ; j <= n-1 ; j++){
        //从第一位一直直到最后一位“还没归位”的数字
        if(a[j] < a[j+1]){
            t = a[j];
            a[j] = a [j+1];
            a[j+1] = t ;
            //比较大小并交换，交换过程中t只是一个工具罢了
        }
    }
}
//这样就完成了冒泡排序了

//下面输出试试
for(i = 1 ; i<= n ;i++){
    printf("%d",a[i]);
}

上述代码中，在循环里。i代表的是我们要执行的冒泡的最大次数，如前文所说n个数字的排序，我们进行n-1趟冒泡，而j则是进行每一轮的遍历搜索
实质上这个过程还可以被优化，比如说检查是否已经排序完成，检查每轮每趟的任务是否不用进行等等。这样的优化虽然不会降低复杂度，但会在一下情况下节约时间、提高效率
这里我们只是介绍冒泡，就不再细说了

快速排序

快速排序的核心是基准数，基准数理论上是可以随机的一个数，这里我们每次都选择第一个/最左边的数作为基准数

我们可以认为，快速排序的过程，就是不断选择基准数排序的过程。我们大致可以这么描述它的步骤：
【比如我们排序 6 1 2 7 9 3 4 5 10 8 】
1.选择一个数作为基准数，我们这里就是6
2.派出两个变量去“搜索”比6大的数，和比6小的数。这里我们设置变量为i与j
3.i和j从两头开始搜索，i从最左边（第0位），而j从最右边(最后一位)
4.i从左向右搜索，j从右向左进行搜索。当二者都成功找到后，交换这两个变量指向的数值
5.比如，第一次交换后，我们得到
【6 1 2 7 9 3 4 5 10 8】
【6 1 2 5 9 3 4 7 10 8】
(由于我们要从小到大排序，因此让小的数在左边)
6.继续让i向右搜索而j向左搜索，这里我们可以再次得到以此9和4的交换，器结果为：
【6 1 2 5 4 3 9 7 10 8】
这时候我们的两个用来探索的变量已经即将“遇上”，如果此时我们没有找到其它的相互交换的数值，则算结束了一轮搜索
7.把它们相遇的位置和最开始的基准数交换，这里就是3和6互换
8.此时的序列变成 3 1 2 5 4 6 9 7 10 8
9.此时我们可以发现：这个序列变成了一个以6为分界点的序列，左边都比它小而右边都比它大。这正是我们的目的。
10.对6的左边和右边一直重复2-9的过程，直到所有数字完成排序

代码示例

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
int a[101],n ; //需要在子函数里面使用的全局变量

void quicksort(int left , int right){
    int i,j,t,temp ; 
    if(left>right)  return ;

    temp = a[left]; //temp中存储我们的基准数
    i = left ; 
    j = right ; 
    while(i!=j){
        //记住顺序：我们需要先“从右往左”找
        while(a[j] >= temp && i<j)  
            j-- ;//没找到比基准数小的数就继续推进
            //找到了当然就可以开始i的遍历

        //再“从左往右”找
        while(a[i] <= temp && i<j)  
            i++ ;//没找到比基准数大的数就继续推进

        //交换两个数在数组中的位置
        if(i<j){
            //当二者“还没有相遇”
            t = a[i] ; 
            a[i]=a[j];
            a[j] = t ;
        }
    }

    //将基准数归位
    a[left] = a[i] ;
    a[i] = temp ;

    quicksort(left,i-1);   //继续处理左边的，这里是一个递归
    quicksort(i+1,right) ; //同理，继续递归处理右边
    return

}

int main(){
    int i , j ;
    scanf("%d",&n) ;   //读入数据
    for(i = 1 ; i<= n ;i++){
        scanf("%d",&a[i]);
    }

    quicksort(1,n);

    //输出结果
    for(i = 1 ; i <= n ;i++){
        printf("%d",a[i]);
    }

    getchar();getchar();
    return 0 ;
}