算法--排序算法整理

排序概念

排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。

各种排序

以下的排序都是以排序数组为例。当然一般用来排序的也就是数组了，比如栈，队列，哈系表这些，
就不用排序了，因为它们的主要用途不在于排序。

首先中间的交换函数是用一个通用的交换函数

1
2
3
4
5
6
7
8
9
void swap(void *a, void *b, int size)
{
    void *temp = malloc(size);
    memcpy(temp, a, size);
    memcpy(a, b, size);
    memcpy(b, temp, size);
    
    free(temp);
}

选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void select_sort(int *array, int length);
void select_sort(int *array, int length)
{
    int i = 0;
    int j = 0;
    
    for(i = 0; i < length - 1; ++i){
        for(j = i + 1; j < length; ++j){
            if(array[i] > array[j]){
                swap(array + i, array + j, sizeof(array[i]));
            }
        }
    }  
}

直接插入排序

1
2
3
4
5
6
7
8
9
10
11
12
void insert_sort(int *array, int length);
void insert_sort(int *array, int length)
{
    int i = 0;
    int j = 0;

    for(i = 1; i < length; ++i){
        for(j = i - 1; j >= 0 && array[j] > array[j + 1]; --j){
            swap(&array[j], &array[j + 1], sizeof(array[j]));
        }
    }
}

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void bubble_sort(int *array, int length);
void bubble_sort(int *array, int length)
{
    int i = 0;
    int j = 0;
  
    for(i = 0; i < length - 1; ++i){
        for(j = 0; j < length - i - 1; ++j){
            if(array[j] > array[j + 1]){
                swap(array + j, array + j + 1, sizeof(array[j]));
            }
        }
    }
}

冒泡排序（改进）

改进思路，冒泡排序可能排到一半就已经排列好了，当一次冒泡过程中没有发生交换
说明已经排好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void bubble_sort(int *array, int length);
void bubble_sort(int *array, int length)
{
    int i = 0;
    int j = 0;
    int flag = 0;
    
    for(i = 0; i < length - 1; ++i){
        flag = 0;
        for(j = 0; j < length - i - 1; ++j){
            if(array[j] > array[j + 1]){
                swap(array + j, array + j + 1, sizeof(array[j]));
                flag = 1;
            }
        }
        //如果flag为0，说明没有发生交换
        if(flag == 0){
            break;
        }
    }
}

快速排序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
30
31
32
33
34
void quick_sort(int *array, int length);
void quick_sort(int *array, int length)
{
    int i = 0;
    int j = 0;
    int value = 0;
    
    if(length > 1){
        i = 0;
        j = length - 1;
        value = array[0];
        while(i < j){
            while(i < j){
                if(array[j] < value){
                    array[i++] = array[j];
                    break;
                }
                j--;
            }
            
            while(i < j){
                if(array[i] > value){
                    array[j--] = array[i];
                    break;
                }
                i++;
            }
        }
        array[i] = value;
        quick_sort(array, i);
        quick_sort(array + i + 1, length - i - 1);
    }
    
}

老师曾经说过，循环里面加if会使程序的效率遍低，所以可以稍微改进一下

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
void quick_sort(int *array, int length)
{
    int i = 0;
    int j = 0;
    int value = 0;
    
    if(length > 1){
        i = 0;
        j = length - 1;
        value = array[0];
        while(i < j){
            while(i < j && array[j] > value){
                j--;
            }
            if(i < j){
                array[i++] = array[j];
            }
            while(i < j && array[i] < value){
                i++;
            }
            if(i < j){
                array[j--] = array[i];;
            }
        }
        array[i] = value;
        quick_sort(array, i);
        quick_sort(array + i + 1, length - i - 1);
    }
    
}

虽然这样循环里面仍然有if但是，if在外层的循环，之前的if是在里层的循环，所以这样效率会高

快速排序2

这种快速排序时早期的快排，也是算法导论这本书上所讲到的快速排序。
以最后一个元素作为基准，i是此时小于标准的最大的下标，初始为-1。
j从头开始遍历到倒数第二个元素，找到小的元素就将i++，并交换i和j所指向的元素
当遍历完后，把把i+1对应的元素和最后一个元素交换，这样i+1前面的数都要比i+1后面的数要小

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void quick_sort(int *array, int length);
void quick_sort(int *array, int length)
{
    int i = -1;
    int j = 0;
    int value = 0;
    
    if(length > 1){
        value = array[length - 1];
        for(j = 0; j < length - 1; ++j){
            if(array[j] <= value){
                i++;
                swap(&array[i], &array[j], sizeof(array[i]));
            }
        }
        swap(&array[i + 1], &array[length - 1], sizeof(array[i + 1]));
        quick_sort(array, i + 1);
        quick_sort(array + i + 2, length - i - 2);
    }
}

这个版本的快速排序，虽然代码看起来要比第一种要简洁，但是这个用到了交换操作，所以效率会低点

归并排序

归并排序是建立在归并操作上的一种有效的排序算法,
该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，
再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

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
void merge_sort(int *array, int length);
void merge_sort(int *array, int length)
{
    int i = 0;
    int j = 0;
    int cnt = 0;
    int *temp_array = NULL;
    if(length > 1){
        //新建临时的数组用来二路归并
        temp_array = (int *)malloc(sizeof(int) * length);
        merge_sort(array, length / 2);
        merge_sort(array + length / 2, length - length / 2);
        i = 0;
        j = length / 2;
        while(i < length / 2 && j < length){
            if(array[i] < array[j]){
                temp_array[cnt++] = array[i++];
            }else{
                temp_array[cnt++] = array[j++];
            }
        }
        while(i < length / 2){
            temp_array[cnt++] = array[i++];
        }
        while(j < length){
            temp_array[cnt++] = array[j++];
        }
        for(i = 0; i < length; ++i){
            array[i] = temp_array[i];
        }
        free(temp_array);
    }
}

希尔排序

希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，
是直接插入排序算法的一种更高效的改进版本。
希尔排序是非稳定排序算法。
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；
随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void shell_sort(int *array, int length);
void shell_sort(int *array, int length)
{
    int i = 0;
    int j = 0;
    int gap = length;
    while(gap = gap / 2){
        for(i = gap; i < length; ++i){
            for(j = i - gap; j >= 0 && array[j] > array[j + gap]; j = j - gap){
                swap(array + j, array + j + gap, sizeof(int));
            }
        }
    }
}

Shell排序是一种不稳定的排序算法，其时间复杂度受增量序列的影响明显大于其他因素，
最坏的情况是o(n2)，好的情况在o(n1.3)，与增量序列选择有关

计数排序

计数排序可以说不是真正意义上的排序，它是先统计每个元素的个数，然后把元素都展开就好
计数排序在一些特定的情况下使用，当知道最大值，且数值的范围较为集中，且，必须为正数，
当然其实也可以对负数专门再弄一个数组来存。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void count_sort(int *array, int length, int max);
void count_sort(int *array, int length, int max)
{
    int *count = (int *)malloc(sizeof(int) * (max + 1));
    int cnt = 0;
    int i = 0;
    bzero(count, sizeof(int) * (max + 1));
    //统计每个数的个数，下标代表数，对应的元素的值代表个数
    for(i = 0; i < length; ++i){
        count[array[i]]++;
    }
    for(i = 0; i <= max; ++i){
        while(count[i]--){
            array[cnt++] = i;
        }
    }
}

基数排序

基数排序也是一种不用比较的排序，每次只排一位，从个位，十位，百位。。。
直到最后一位。然而，比较一位并不需要比较，只要把它放到对应下标的数组就好了。
当所有的位都排好，这个序列也就排好了。

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
void radix_sort(int *array, int length);
void radix_sort(int *array, int length)
{
    int i = 0;
    int k = 0;
    int t = 1;
    int j = 0;
    int cnt = 0;
    
    //创建十个用来存放数的数组，小标0-9
    int ** con = (int **)malloc(sizeof(int *) * 10);
    for(i = 0; i < 10; ++i){
        con[i] = (int *)malloc(sizeof(int) * (length + 1));
        bzero(con[i], sizeof(int) * (length + 1));
    }
    
    //用t的累增来表示从个位到最高位的取值，这里默认最高位8位
    while(t < 100000000){
        for(i = 0; i < length; ++i){
            k = array[i] / t % 10;
            //用每个数组的第一位用来存放每个数组的个数
            con[k][++con[k][0]] = array[i];
        }
        cnt = 0;
        //把收集好的每个数都重新展开原数组
        for(i = 0; i < 10; ++i){
            for(j = 1; j <= con[i][0]; ++j){
                array[cnt++] = con[i][j];
            }
            con[i][0] = 0;
        }
        t = t * 10;
    }
    for(i = 0; i < 10; ++i){
        free(con[i]);
    }
    free(con);
}

Title:算法--排序算法整理

Author:Jin Feng

Created:2015-09-23, 16:50:51

Updated:2016-05-09, 09:40:47

Full URL:http://0x00000000.cn/2015/09/23/算法-排序算法整理/

License: "CC BY-NC-SA 4.0" Keep Link & Author if Distribute.

Contents
  1. 1. 排序概念
  2. 2. 各种排序
    1. 2.1. 选择排序
    2. 2.2. 直接插入排序
    3. 2.3. 冒泡排序
    4. 2.4. 冒泡排序（改进）
    5. 2.5. 快速排序1
    6. 2.6. 快速排序2
    7. 2.7. 归并排序
    8. 2.8. 希尔排序
    9. 2.9. 计数排序
    10. 2.10. 基数排序
,