算法-排序

发表于 | 分类于 | | 阅读次数

头文件如下:

1
2
3
4
5
6
#define OK 0
#define ERROR -1
#define TRUE 1
#define FALSE 0
#define NULL (void*)0
typedef int Status;

交换两个变量的值

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
void Swap(int& a, int& b)
{
    #if 0
    a = a + b - (b = a);
    #endif
    #if 0
    b = a + (a = b) * 0;
    #endif
    #if 0
    a = a + b;
    b = a - b;
    a = a - b;
    #endif
    #if 0
    a = a * b;
    b = a / b;
    a = a / b;
    #endif
    #if 1
    a = a ^ b;
    b = a ^ b;
    a = a ^ b;
    #endif
}

插入排序

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
/*
性能:
    1）稳定
    2）空间代价：O(1)
    3）时间代价：
步骤:
    1、从第一个元素开始，该元素可以认为已经被排序
    2、取出下一个元素，在已经排序的元素序列中从后向前扫描
    3、如果该元素（已排序）大于新元素，将该元素移到下一位置
    4、重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
    5、将新元素插入到该位置后
    6、重复步骤2~5
*/
Status InsertSort(int array[], int len)
{
    if (NULL == array) {
        return ERROR;
    }
    register int i, j, temp;
    for (i = 1; i < len; i++)
    {
        temp = array[i];
        j = i-1;    //key1. before the current location
        while ((j >= 0) && (array[j] > temp))
        {
            array[j+1] = array[j];
            j--;
        }
        array[j+1] = temp;  //key2. pay attention to 'j+1'
    }
    return OK;
}

二分插入排序

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
/*
性能:
    1）稳定
    2）空间代价：O(1)
    2）时间间代价：
步骤:
    1、从第一个元素开始，该元素可以认为已经被排序
    2、取出下一个元素，在已经排序的元素序列中二分查找到第一个比它大的数的位置
    3、将新元素插入到该位置后
    4、重复上述两步
*/
Status BinInsertSort(int array[], int len)
{
    if (NULL == array) {
        return ERROR;
    }
    register int i, j, temp, left, right, mid;
    for (i = 1; i < len; i++)
    {
        temp = array[i];
        left = 0;
        right = i-1;
        while (left <= right)
        {
            mid = (left + right)/2;
            if (array[mid] > temp)
                right = mid-1;
            else
                left = mid+1;
        }//key. 此时left肯定就是待插入的位置坐标
        for (j = i-1; j > left; j--)
        {
            array[j+1] = array[j];
        }
        array[left] = temp;
    }
    return OK;
}

希尔排序

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
/*
性能:
    1）
    2）空间代价：
    2）时间间代价：
步骤:
    1、先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。
    2、所有距离为d1的倍数的记录放在同一个组中，在各组内进行直接插入排序。
    3、取第二个增量d2<d1重复上述的分组和排序，
    4、直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。
*/
Status ShellSort1(int array[], int len)
{
    register int i, j, k, gap, temp;
    for (gap = len/2; gap > 0; gap /= 2) //步长
    {
        for (i = 0; i < gap; i++) //直接插入排序 - 执行 gap 趟
        {
            for (j = i + gap; j < len; j += gap)
            {
                if (array[j] < array[j - gap])
                {
                    temp = array[j];
                    k = j - gap;
                    while (k > 0 && array[k] > temp)
                    {
                        array[k + gap] = array[k];
                        k -= gap;
                    }
                    array[k + gap] = temp;
                }
            }
        }
    }
    return OK;
}

选择排序

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
/*
性能:
    1）稳定
    2）空间代价：O(1)
    2）时间间代价：
步骤:
    1、初始状态：无序区为R[1..n]，有序区为空。
    2、第i趟排序(i=1,2,3...n-1)
       第i趟排序开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。
       该趟排序从当前无序区中选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，
       使R[1..i]和R分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
    3、前n-1趟结束，数组有序化了
*/
Status SelectSort(int array[], int len)
{
    if (NULL == array) {
        return ERROR;
    }
    register int i, j, min;
    for (i = 0; i < len - 1; i++)
    {
        min = i;
        for (j = i+1; j < len; j++)
        {
            if (array[min] > array[j]) {
                min = j;
            }
        }
        Swap(array[i], array[min]);
    }
    return OK;
}

堆排序

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
/*
性能:
    1）
    2）空间代价：
    2）时间间代价：
步骤:
    一般都用数组来表示堆，i结点的父结点下标为(i-1)/2，左右子结点的下标分别为 2*i + 1和 2*i + 2
    堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。
    堆即是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
1. 什么是堆?
    我们这里提到的堆一般都指的是二叉堆，它满足二个特性：
        1>父结点的键值总是大于或等于（小于或等于）任何一个子节点的键值
        2>每个结点的左子树和右子树都是一个二叉堆（都是最大堆或最小堆）
2、什么是堆调整(Heap Adjust)？
    这是为了保持堆的特性而做的一个操作。对某一个节点为根的子树做堆调整，其实就是将该根节点进行“下沉”操作
    (具体是通过和子节点交换完成的)，一直下沉到合适的位置，使得刚才的子树满足堆的性质。
    例如对最大堆的堆调整我们会这么做：
        1、在对应的数组元素A[i], 左孩子A[LEFT(i)], 和右孩子A[RIGHT(i)]中找到最大的那一个，将其下标存储在largest中。
        2、如果A[i]已经就是最大的元素，则程序直接结束。
        3、否则，i的某个子结点为最大的元素，将A[largest]与A[i]交换。
        4、再从交换的子节点开始，重复1,2,3步，直至叶子节点，算完成一次堆调整。
    这里需要提一下的是，一般做一次堆调整的时间复杂度为log(n)。
3、如何建堆?
    建堆是一个通过不断的堆调整，使得整个二叉树中的数满足堆性质的操作。
    在数组中的话，我们一般从下标为n/2的数开始做堆调整，一直到下标为0的数
    (因为下标大于n/2的数都是叶子节点，其子树已经满足堆的性质了)
4、如何进行堆排序 ?
    堆排序是在上述3中对数组建堆的操作之后完成的。
    数组储存成堆的形式之后，第一次将A[0]与A[n - 1]交换，再对A[0…n-2]重新恢复堆。
    第二次将A[0]与A[n-2]交换，再对A[0…n-3]重新恢复堆，重复这样的操作直到A[0]与A[1]交换。
    由于每次都是将最小的数据并入到后面的有序区间，故操作完成后整个数组就有序了 */
#include<math.h>
int parent(int i){
    return (int)floor((i - 1) / 2);
}
int left(int i){
    return (2 * i + 1)
}
int right(int i){
    return (2 * i + 2)
}
void HeapAdjust(int array[], int i, int heap_size)
{
}

冒泡排序

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
/*
性能:
    1）稳定
    2）空间代价：
    2）时间间代价：
步骤:
    1、比较相邻的元素。如果第一个比第二个大，就交换他们两个。
    2、对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
    3、针对所有的元素重复以上的步骤，除了最后一个。
    4、持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
*/
Status BubbleSort(int array[], int len)
{
    if (NULL == array) {
        return ERROR;
    }
    register int i, j;
    for (i = len; i > 0; i--)
    {
        for (j = 0; j < i-1; j++)
        {
            if (array[j] > array[j+1]) //key 最大的数据沉底
            {
                Swap(array[j], array[j+1]);
            }
        }
    }
    return OK;
}

快速排序

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
/*
性能:
    1）稳定
    2）空间代价：
    2）时间间代价：
步骤:
    1、从数列中挑出一个元素，称为 "基准"（pivot），
    2、重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
    3、递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
*/
int Partition(int* data, int low, int high)
{
    int pivotkey = low;
    while (low < high)
    {
        while (low < high && data[high] > data[pivotkey]) {
            high--;
        }
        Swap(data[low], data[high]);
        while (low < high && data[low] < data[pivotkey]) {
            low++;
        }
        Swap(data[low], data[high]);
    }
    return low;
}
Status QuickSort(int array[], int low, int high)
{
    int pivot;
    if (low < high)
    {
        pivot = Partition(array, low, high);
        QuickSort(array, low, pivot-1);
        QuickSort(array, pivot+1, high);
    }
    return OK;
}

归并排序类