排序算法

Posted on |

排序算法的稳定性：排序算法稳定性的简单形式化定义为：如果Ai = Aj，排序前Ai在Aj之前，排序后Ai还在Aj之前，则称这种排序算法是稳定的。通俗地讲就是保证排序前后两个相等的数的相对顺序不变。（冒泡，直接插入排序，归并排序是稳定的，简单选择排序，希尔排序，堆排序，快排是不稳定的。）

#鸡尾酒排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int A[] = { 6, 5, 3, 1, 8, 7, 2, 4 };   // 从小到大定向冒泡排序
    int n = sizeof(A) / sizeof(int);                
    int left = 0;                           // 初始化边界
    int right = n - 1;
while (left < right)
    {
        for (int i = left; i < right; i++)  // 前半轮,将最大元素放到后面
            if (A[i] > A[i + 1])
            {
                exchange(A, i, i + 1);
            }
        right--;
        for (int i = right; i > left; i--)  // 后半轮,将最小元素放到前面
            if (A[i - 1] > A[i])
            {
                exchange(A, i - 1, i);
            }
        left++;
    }

#冒泡排序

1
2
3
4
5
6
7
8
9
10
11
int A[] = { 6, 5, 3, 1, 8, 7, 2, 4 };    // 从小到大冒泡排序
    int n = sizeof(A) / sizeof(int);                
    for (int j = 0; j < n - 1; j++)            // 每次最大元素就像气泡一样"浮"到数组的最后
    {
        for (int i = 0; i < n - 1 - j; i++)    // 依次比较相邻的两个元素,使较大的那个向后移
        {
            if (A[i] > A[i + 1])            // 如果条件改成A[i] >= A[i + 1],则变为不稳定的排序算法
            {
                exchange(A, i, i + 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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

void exchange(int A[], int i, int j)        // 交换A[i]和A[j]
{
    int temp = A[i];
    A[i] = A[j];
    A[j] = temp;
}

int partition(int A[], int left, int right)  // 划分函数
{
    int pivot = A[right];                    // 选择最后一个元素作为基准
    int tail = left - 1;                     // tail为小于基准的子数组最后一个元素的索引
    for (int i = left; i < right; i++)       // 遍历基准以外的其他元素
    {
        if (A[i] <= pivot)                   // 把小于等于基准的元素放到前一个子数组中
        {
            tail++;
            exchange(A, tail, i);
        }
    }
    exchange(A, tail + 1, right);            // 最后把基准放到前一个子数组的后边,剩下的子数组既是大于基准的子数组
　　　　　　　　　　　　　　　　　　　　　　　　　　// 该操作很有可能把后面元素的稳定性打乱,所以快速排序是不稳定的排序算法
    return tail + 1;                         // 返回基准的索引
}

void quicksort(int A[], int left, int right)
{
    int pivot_index;                        // 基准的索引
    if (left < right)
    {
        pivot_index = partition(A, left, right);
        quicksort(A, left, pivot_index-1);
        quicksort(A, pivot_index+1, right);
    }

}

int main()
{
    int A[] = { 5, 2, 9, 4, 7, 6, 1, 3, 8 };// 从小到大快速排序
    int n = sizeof(A) / sizeof(int);
    quicksort(A, 0, n - 1);
    printf("快速排序结果：");
    for (int i = 0; i < n; i++)
    {
        printf("%d ",A[i]);
    }
    printf("\n");
    return 0;
}

#插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

int A[] = { 6, 5, 3, 1, 8, 7, 2, 4 };// 从小到大插入排序
    int n = sizeof(A) / sizeof(int);
    int i, j, get;

    for (i = 1; i < n; i++)             // 类似抓扑克牌排序
    {
        get = A[i];                     // 右手抓到一张扑克牌
        j = i - 1;                      // 拿在左手上的牌总是排序好的
        while (j >= 0 && A[j] > get)    // 将抓到的牌与手牌从右向左进行比较
        {
            A[j + 1] = A[j];            // 如果该手牌比抓到的牌大,就将其右移
            j--;
        }
        A[j + 1] = get;// 直到该手牌比抓到的牌小(或二者相等),将抓到的牌插入到该手牌右边(相等元素的相对次序未变,所以插入排序是稳定的)
    }

#二分插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

int A[] = { 5, 2, 9, 4, 7, 6, 1, 3, 8 };// 从小到大二分插入排序
    int n = sizeof(A) / sizeof(int);
    int i, j, get, left, right, middle;

    for (i = 1; i < n; i++)                 // 类似抓扑克牌排序
    {
        get = A[i];                         // 右手抓到一张扑克牌
        left = 0;                           // 拿在左手上的牌总是排序好的,所以可以用二分法
        right = i - 1;                      // 手牌左右边界进行初始化
        while (left <= right)               // 采用二分法定位新牌的位置
        {
            middle = (left + right) / 2;
            if (A[middle] > get)
                right = middle - 1;
            else
                left = middle + 1;
        }
        for (j = i - 1; j >= left; j--)    // 将欲插入新牌位置右边的牌整体向右移动一个单位
        {
            A[j + 1] = A[j];            
        }
        A[left] = get;                    // 将抓到的牌插入手牌
    }

#希尔排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int A[] = { 5, 2, 9, 4, 7, 6, 1, 3, 8 };// 从小到大希尔排序
    int n = sizeof(A) / sizeof(int);
    int i, j, get;
    int h = 0;
    while (h <= n)                          // 生成初始增量
    {
        h = 3*h + 1;
    }
    while (h >= 1)
    {
        for (i = h; i < n; i++)
        {
            j = i - h;
            get = A[i];
            while ((j >= 0) && (A[j] > get))
            {
                A[j + h] = A[j];
                j = j - h;
            }
            A[j + h] = get;
        }
        h = (h - 1) / 3;                    // 递减增量
    }

#归并排序

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
int L[10];    // 两个子数组定义成全局变量（辅助存储空间,大小正比于元素的个数）
int R[10];

void merge(int A[], int left, int middle, int right)// 合并两个已排好序的数组A[left...middle]和A[middle+1...right]
{
    int n1 = middle - left + 1;     // 两个数组的大小
    int n2 = right - middle;
    for (int i = 0; i < n1; i++)    // 把两部分分别拷贝到两个数组中
        L[i] = A[left + i];
    for (int j = 0; j < n2; j++)
        R[j] = A[middle + j + 1];
    L[n1] = INT_MAX;                // 使用无穷大作为哨兵值放在子数组的末尾
    R[n2] = INT_MAX;                // 这样可以免去检查某个子数组是否已读完的步骤
    int i = 0;
    int j = 0;
    for (int k = left; k <= right; k++) // 依次比较两个子数组中的值，每次取出更小的那一个放入原数组
    {
        if (L[i] <= R[j])
        {
            A[k] = L[i];
            i++;
        }
        else
        {
            A[k] = R[j];
            j++;
        }
    }

}

void mergesort_recursion(int A[], int left, int right) // 递归实现的归并排序(自顶向下)
{
    int middle = (left + right) / 2;
    if (left < right)          // 当待排序的序列长度为1时(left == right)，递归“开始回升”
    {
        mergesort_recursion(A, left, middle);
        mergesort_recursion(A, middle + 1, right);
        merge(A, left, middle, right);
    }
}

void mergesort_iteration(int A[], int left, int right)  // 非递归(迭代)实现的归并排序(自底向上)
{
    int low, middle, high;    // 子数组索引,前一个为A[low...middle],后一个子数组为A[middle+1...high]
    for (int size = 1; size <= right - left; size *= 2) // 子数组的大小初始为1,每轮翻倍
    {
        low = left;
        while (low + size - 1 <= right - 1 )// 后一个子数组存在(需要归并)
        {
            middle = low + size - 1;    
            high = middle + size;        
            if (high > right)            　　// 后一个子数组大小不足size
                high = right;
            merge(A, low, middle, high);
            low = high + 1;                　// 前一个子数组索引向后移动
        }
    }
}

int main()
{
    int A1[] = { 6, 5, 3, 1, 8, 7, 2, 4 };    // 从小到大归并排序
    int A2[] = { 6, 5, 3, 1, 8, 7, 2, 4 };    
    int n1 = sizeof(A1) / sizeof(int);
    int n2 = sizeof(A2) / sizeof(int);
    mergesort_recursion(A1, 0, n1 - 1);       // 递归实现
    mergesort_iteration(A2, 0, n2 - 1);       // 非递归实现
    printf("递归实现的归并排序结果：");
    for (int i = 0; i < n1; i++)
    {
        printf("%d ",A1[i]);
    }
    printf("\n");
    printf("非递归实现的归并排序结果：");
    for (int i = 0; i < n2; i++)
    {
        printf("%d ", A2[i]);
    }
    printf("\n");
    return 0;
}

#堆排序

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
64
65
66
67
68
#include <stdio.h>

// 分类 -------------- 内部比较排序
// 数据结构 ---------- 数组
// 最差时间复杂度 ---- O(nlogn)
// 最优时间复杂度 ---- O(nlogn)
// 平均时间复杂度 ---- O(nlogn)
// 所需辅助空间 ------ O(1)
// 稳定性 ------------ 不稳定

int heapsize;    // 堆大小

void exchange(int A[], int i, int j)    // 交换A[i]和A[j]
{
    int temp = A[i];
    A[i] = A[j];
    A[j] = temp;
}

void heapify(int A[], int i)            // 堆调整函数(这里使用的是最大堆)
{
    int leftchild = 2 * i + 1;          // 左孩子索引
    int rightchild = 2 * i + 2;         // 右孩子索引
    int largest;                        // 选出当前结点与左右孩子之中的最大值
    if (leftchild < heapsize && A[leftchild] > A[i])
        largest = leftchild;
    else
        largest = i;
    if (rightchild < heapsize && A[rightchild] > A[largest])
        largest = rightchild;
    if (largest != i)                    
    {
        exchange(A, i, largest);        // 把当前结点和它的最大(直接)子节点进行交换
        heapify(A, largest);            // 递归调用，继续从当前结点向下进行堆调整
    }
}

void buildheap(int A[], int n)          // 建堆函数
{
    heapsize = n;
    for (int i = heapsize / 2 - 1; i >= 0; i--) // 对每一个非叶结点
        heapify(A, i);                  // 不断的堆调整
}

void heapsort(int A[], int n)
{
    buildheap(A, n);
    for (int i = n - 1; i >= 1; i--)
    {
        exchange(A, 0, i); // 将堆顶元素(当前最大值)与堆的最后一个元素互换(该操作很有可能把后面元素的稳定性打乱,所以堆排序是不稳定的排序算法)
        heapsize--;                     // 从堆中去掉最后一个元素
        heapify(A, 0);                  // 从新的堆顶元素开始进行堆调整
    }
}

int main()
{
    int A[] = { 5, 2, 9, 4, 7, 6, 1, 3, 8 };// 从小到大堆排序
    int n = sizeof(A) / sizeof(int);
    heapsort(A, n);
    printf("堆排序结果：");
    for (int i = 0; i < n; i++)
    {
        printf("%d ", A[i]);
    }
    printf("\n");
    return 0;
}