11_排序算法

数据结构和算法

11.1 排序算法

11.1.1 排序的基本概念与分类

• 概念

  • 假设含有n个记录的序列为{r1, r2, ..., rn}，其相应的关键字分别为{k1, k2, ..., kn}，需确定1, 2, ..., n 的一种排列 p1, p2, ..., pn，使其相应的关键字满足 Kp1<=Kp2<=..<=Kpn 非递减（或非递增）关系，即使得序列成为一个按关键字有序的序列{rp1, rp2, ..., rpn}，这样的操作就称为排序。

• 在排序问题中，通常将数据元素称为记录。

  • 显然我们输入的是一个记录集合，排序后输出的也是一个记录集合。
  • 所以我们可以将排序看成是线性表的一种操作。

• 排序的依据是关键字之间的大小关系，那么对同一记录集合，针对不同的关键字进行排序，可以得到不同的序列。

• 分类

  • 插入排序类

    • 直接插入排序
    • 希尔排序

  • 选择排序类

    • 简单选择排序
    • 堆排序

  • 交换排序类

    • 冒泡排序
    • 快速排序

  • 归并排序类

    • 归并排序

11.1.2 排序的稳定性

• 假设ki=kj（1<=i<=n, 1<=j<=n, i!=j），且在排序前的序列中ri领先于rj（即i
  • 如果排序后ri仍领先于rj，则称所用的排序方法是稳定的；
  • 反之，若可能使得排序后的序列中rj领先ri，则称所用的排序方法是不稳定的。

11.1.3 影响排序算法性能的几个要素

• 时间性能
• 辅助空间
• 算法的复杂性

11.2 冒泡排序

• 冒泡排序的要点

  • 两两注意是相邻的两个元素的意思
  • 如果有n个元素需要比较n-1次，每一轮减少1次比较
  • 既然叫冒泡排序，那就是从下往上两两比较，所以看上去就跟泡泡往上冒一样

• 代码实现

#include <stdio.h>
void BubbleSort(int k[], int n)
{
    int i, j, temp, count1=0, count2=0;
    for( i=0; i < n-1; i++ )
    {
        for( j=i+1; j < n; j++ )
        {
            count1++;
            if( k[i] > k[j] )
            {
                count2++;
                temp = k[j];
                k[j] = k[i];
                k[i] = temp;
            }
        }
    }
    printf("总共进行了%d次比较，进行了%d次移动！\n", count1, count2);
}
int main()
{
    int i;
    int a[10] = {5, 2, 6, 0, 3, 9, 1, 7, 4, 8};
    BubbleSort(a, 10);
    printf("排序后的结果是： \n");
    for( i=0; i < 10; i++ )
    {
        printf("%d", a[i]);
    }
    printf("\n");
    return 0;
}

• 优化版

#include <stdio.h>
void BubbleSort(int k[], int n)
{
    int i, j, temp, count1=0, count2=0;
    int flag = 1;
    for( i=0; i < n-1 && flag; i++ )
    {
        for( j=n-1; j > i; j-- )
        {
            count1++;
            flag = 0; 
            if( k[j-1] > k[j] )
            {
                count2++;
                temp = k[j-1];
                k[j-1] = k[j];
                k[j] = temp;
                flag = 1;
            }
        }
    }
    printf("总共进行了%d次比较，进行了%d次移动！\n", count1, count2);
}
int main()
{
    int i;
    int a[10] = {5, 2, 6, 0, 3, 9, 1, 7, 4, 8};
    BubbleSort(a, 10);
    printf("排序后的结果是： \n");
    for( i=0; i < 10; i++ )
    {
        printf("%d", a[i]);
    }
    printf("\n");
    return 0;
}

11.3 选择排序

• 选择排序算法就是通过n-i次关键字间的比较，从n-i+1个记录中最小的记录，并和第i（1<=i<=n）个记录交换。

• 代码实现

#include <stdio.h>
void SelectSort(int k[], int n)
{
    int i, j, min, temp, count1=0, count2=0;
    for( i=0; i < n-1; i++ )
    {
        min = i;
         for( j=i+1; j < n; j++ )
         {
            count1++;
            if( k[j] < k[min] )
            {
                min = j;
            }
         }
         if( min != i )
         {
            count2++;
            temp = k[min];
            k[min] = k[i];
            k[i] =  temp;
         }
    }
    printf("总共进行了%d次比较，进行了%d次移动！\n", count1, count2);
}
int main()
{
    int i;
    int a[10] = {5, 2, 6, 0, 3, 9, 1, 7, 4, 8};
    SelectSort(a, 10);
    printf("排序后的结果是： \n");
    for( i=0; i < 10; i++ )
    {
        printf("%d", a[i]);
    }
    printf("\n");
    return 0;
}

11.4 直接插入排序

• 直接插入排序算法（Straight Insertion Sort)的基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增加1的有序表。

• 代码实现

#include <stdio.h>
void InsertSort(int k[], int n)
{
    int i, j, temp;
    for( i=1; i < n; i++ )
    {
        if( k[i] < k[i-1] )
        {
            temp = k[i];
            for( j=i-1; k[j] > temp; j-- )
            {
                k[j+1] = k[j];
            }
            k[j+1] = temp;
        }
    }
}
int main()
{
    int i;
    int a[10] = {5, 2, 6, 0, 3, 9, 1, 7, 4, 8};
    InsertSort(a, 10);
    printf("排序后的结果是： \n");
    for( i=0; i < 10; i++ )
    {
        printf("%d", a[i]);
    }
    printf("\n");
    return 0;
}

11.5 希尔排序

• 一般排序算法的时间复杂度为O(n^2)，希尔排序的时间复杂度为O(n*log n)。

• 代码实现

#include <stdio.h>
void ShellSort(int k[], int n)
{
    int i, j, temp;
    int gap = n;
    do
    {
        gap /= 3;
        for( i=gap; i < n; i++ )
        {
            if( k[i] < k[i-gap] )
            {
                temp = k[i];
                for( j=i-gap; k[j] > temp; j-=gap )
                {
                    k[j+gap] = k[j];
                }
                k[j+gap] = temp;
            }
        }       
    } while(gap > 0);
}
int main()
{
    int i;
    int a[10] = {5, 2, 6, 0, 3, 9, 1, 7, 4, 8};
    ShellSort(a, 10);
    printf("排序后的结果是： \n");
    for( i=0; i < 10; i++ )
    {
        printf("%d", a[i]);
    }
    printf("\n");
    return 0;
}

11.6 堆排序

• 堆，是具有以下性质的完全二叉树

  • 每个结点的值都大于或等于其左右孩子的结点的值，称为大顶堆。
  • 每个结点的值都小于或等于其左右孩子的结点的值，称为小顶堆。

• 要点

  • 根结点一定是堆中所有结点最大或者最小者，如果按照层序遍历的方式给结点从1开始编号，则结点之间满足如下关系：

    • Ki >= K2i 且 Ki >= K2i+1
    • 或 Ki <= K2i 且 Ki <= K2i+1
    • (1<=i<=|n/2|)

  • 下标i与2i和2i+1是双亲和子女关系

  • 那么把大顶堆和小顶堆用层序遍历存入数组，则一定满足上面的表达式。

• 堆排序(Heap Sort）就是利用堆进行排序的算法，它的基本思想是：

  • 将待排序的序列构造成一个大顶堆（或小顶堆）。
  • 此时，整个序列的最大值就是堆顶的根结点。将它移走（就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值）。
  • 然后将剩余的n-1个序列重新构造成一个堆，这样就会得到n个元素中的最大值。
  • 如此反复执行，便能得到一个有序序列了。

• 代码实现

#include <stdio.h>
int count = 0;
void swap(int k[], int i, int j)
{
    int temp;
    temp = k[i];
    k[i] = k[j];
    k[j] = temp;
}
void HeapAdjust(int k[], int s, int n)
{
    int i, temp;
    temp = k[s];
    // i=2*s：左孩子； 2*s+1: 右孩子 
    for( i=2*s; i <= n; i*=2 )
    {   
        count++;
        if( i < n && k[i] < k[i+1] )  // 左孩子小于右孩子
        {
            i++;  // 使得i指向最大的孩子的下标 
        }
        if( temp >= k[i] )  // temp临时存放当前需要调整的双亲。如果大于孩子，则退出循环
        {
            break;
        }
        k[s] = k[i];
        s = i;
    } 
    k[s] = temp;
}
void HeapSort(int k[], int n)
{
    int i;
    // 从下至上，从右至左，层序遍历 
    for( i=n/2; i > 0; i-- )
    {
        HeapAdjust(k, i, n); // 构建大顶堆的函数。 k:数组 i:当前双亲结点； n:长度
    } 
    for( i=n; i > 1; i-- )
    {
        swap(k, 1, i);  // 调整，将第一个元素和最后一个元素进行互换，i是变化的 
        HeapAdjust(k, 1, i-1);  // 重新调整                                                                                                                                                                                                        
    }
}
int main()
{
    int i;
    int a[10] = {-1, 5, 2, 6, 0, 3, 9, 1, 7, 4};
    HeapSort(a, 9);
    printf("总共执行 %d 次比较! \n", count);
    printf("排序后的结果是： ");
    for( i=1; i < 10; i++ )
    {
        printf("%d ", a[i]);
    }
    printf("\n");
    return 0;
}

11.7 归并排序

• 归并排序（Merge Sort）就是利用归并的思想实现的排序方法。它的原理是假设初始有n个记录，则可以看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到[n/2]个长度为2或1的有序子序列；然后再两两归并，……，如此重复，直至得到一个长度为n的有序序列为止，这种排序方法称为2路归并排序。

• 归并排序的递归实现

// 递归实现
#include <stdio.h>
#define MAXSIZE 10
//实现归并，并把最后的结果存放到list1数组
void merging(int *list1, int list1_size, int *list2, int list2_size)
{
    int i, j, k, m;
    int temp[MAXSIZE];
    i = j = k = 0
    while( i < list1_size && j < list2_size )
    {
        if( list1[i] < list2[j] )
        {
            temp[k++] = list1[i++];
        }
        else
        {
            temp[k++] = list2[j++];
        }
    }
    while( i < list1_size )
    {
        temp[k++] = list1[i++];
    }
    while( j < list2_size )
    {
        temp[k++] = list2[j++];
    }
    for( m=0; m < (list1_size + list2_size); m++ )
    {
        list1[m] = temp[m];
    }
}
void MergeSort(int k[], int n)
{
     if( n > 1 )
     {
        int *list1 = k;
        int list1_size = n/2;
        int *list2 = k + n/2;  // 左半部分的地址加上左半部分的尺寸
        int list2_size = n - list1_size;
        MergeSort(list1, list1_size);
        MergeSort(list2, list2_size);
        merging(list1, list1_size, list2, list2_size);
    }       
}
int main()
{
    int i;
    int a[10] = {5, 2, 6, 0, 3, 9, 1, 7, 4, 8};
    MergeSort(a, 10);
    printf("排序后的结果是： \n");
    for( i=0; i < 10; i++ )
    {
        printf("%d", a[i]);
    }
    printf("\n");
    return 0;
}

• 归并排序的迭代实现

// 迭代实现
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 10
void MergeSort(int k[], int n)
{
     int i, next, left_min, left_max, right_min, right_max; 
     // 申请空间存放数组
     int *temp = (int *)malloc(n * sizeof(int));
     // 逐级递增比较
     for( i=1; i < n; i*=2 ) // 步长i
     {
        for( left_min=0; left_min < n-i; left_min = right_max )
        {
            right_min = left_max = left_min + i;
            right_max = left_max + i;
            // 右边的下标最大值只能为n，防止越界
            if( right_max > n )
            {
                right_max = n;
            }
            // temp数组的下标，由于每次数据都有返回到k，因此每次都需重新置零
            next = 0;
            // 如果左边的数据还没有到分割线且右边的数据也没有到分割线，则循环
            while( left_min < left_max && right_min < right_max )
            {
                if( k[left_min] < k[right_min] )
                {
                    temp[next++] = k[left_min++]; // 存放较小者
                }
                else
                {
                    temp[next++] = k[right_min++];
                }
            }
            // 如果左边的游标没有到达分割线，则需要把数组接回去
            // 如果右边的游标没有到达分割线，则说明右边的数据比较大，不需要移动位置
            while( left_min < left_max )
            {
                k[--right_min] = k[--left_max];
            }
            while( next > 0 )
            {
                // 将排好序的数组返回给k
                 k[--right_min] = temp[--next];
            }
        }
     }
} 
int main()
{
    int i;
    int a[10] = {5, 2, 6, 0, 3, 9, 1, 7, 4, 8};
    MergeSort(a, 10);
    printf("排序后的结果是： \n");
    for( i=0; i < 10; i++ )
    {
        printf("%d", a[i]);
    }
    printf("\n");
    return 0;
}

11.8 快速排序

• 代码实现

#include <stdio.h>
void swap(int k[], int low, int high)
{
    int temp;
    temp = k[low];
    k[low] = k[high];
    k[high] = temp;
}
int Partition(int k[], int low, int high)
{
    int point;
    point = k[low];
    while( low < high )
    {
        while( low < high && k[high] >= point )
        {
            high--;
        }
        swap(k, low, high);
        while( low < high && k[low] <= point )
        {
            low++;
        }
        swap(k, low, high);
    }
    return low;
}
void QSort(int k[], int low, int high)
{
    int point;
    if( low < high )
    {
        point = Partition(k, low, high);  // 计算基准点，将小于基准点的数放在左边，大的放在右边
        QSort(k, low, point-1);
        QSort(k, point+1, high);
    }
}   
void QuickSort(int k[], int n)
{
    QSort(k, 0, n-1);
} 
int main()
{
    int i;
    int a[10] = {5, 2, 6, 0, 3, 9, 1, 7, 4, 8};
    QuickSort(a, 10);
    printf("排序后的结果是： \n");
    for( i=0; i < 10; i++ )
    {
        printf("%d", a[i]);
    }
    printf("\n");
    return 0;
}

11.8.1 快速排序的优化

11.8.1.1 优化选取基准点

• 三数取中法

#include <stdio.h>
void swap(int k[], int low, int high)
{
    int temp;
    temp = k[low];
    k[low] = k[high];
    k[high] = temp;
}
int Partition(int k[], int low, int high)
{
    int point;
    int m = low + (high-low)/2;
    if( k[low] > k[high] )
    {
        swap(k, low, high);
    }
    if( k[m] > k[high] )
    {
        swap(k, m, high);
    }
    if( k[m] > k[low] )
    {
        swap(k, m, low);
    }
    // 将low变成中间值
    point = k[low];
    while( low < high )
    {
        while( low < high && k[high] >= point )
        {
            high--;
        }
        swap(k, low, high);
        while( low < high && k[low] <= point )
        {
            low++;
        }
        swap(k, low, high);
    }
}
void QSort(int k[], int low, int high)
{
    int point;
    if( low < high )
    {
        point = Partition(k, low, high);  // 计算基准点，将小于基准点的数放在左边，大的放在右边
        QSort(k, low, point-1);
        QSort(k, point+1, high);
    }
}   
void QuickSort(int k[], int n)
{
    QSort(k, 0, n-1);
} 
int main()
{
    int i;
    int a[10] = {5, 2, 6, 0, 3, 9, 1, 7, 4, 8};
    QuickSort(a, 10);
    printf("排序后的结果是： \n");
    for( i=0; i < 10; i++ )
    {
        printf("%d", a[i]);
    }
    printf("\n");
    return 0;
}

11.8.1.2 优化不必要的交换

#include <stdio.h>
void swap(int k[], int low, int high)
{
    int temp;
    temp = k[low];
    k[low] = k[high];
    k[high] = temp;
}
int Partition(int k[], int low, int high)
{
    int point;
    int m = low + (high-low)/2;
    if( k[low] > k[high] )
    {
        swap(k, low, high);
    }
    if( k[m] > k[high] )
    {
        swap(k, m, high);
    }
    if( k[m] > k[low] )
    {
        swap(k, m, low);
    }
    // 将low变成中间值
    point = k[low];
    while( low < high )
    {
        while( low < high && k[high] >= point )
        {
            high--;
        }
        k[low] = k[high];
        while( low < high && k[low] <= point )
        {
            low++;
        }
        k[high] = k[low];
    }
    k[low] = point;
}
void QSort(int k[], int low, int high)
{
    int point;
    if( low < high )
    {
        point = Partition(k, low, high);  // 计算基准点，将小于基准点的数放在左边，大的放在右边
        QSort(k, low, point-1);
        QSort(k, point+1, high);
    }
}   
void QuickSort(int k[], int n)
{
    QSort(k, 0, n-1);
} 
int main()
{
    int i;
    int a[10] = {5, 2, 6, 0, 3, 9, 1, 7, 4, 8};
    QuickSort(a, 10);
    printf("排序后的结果是： \n");
    for( i=0; i < 10; i++ )
    {
        printf("%d", a[i]);
    }
    printf("\n");
    return 0;
}

11.8.1.3 优化小数组时的排序方案

#include <stdio.h>
#define MAX_LENGTH_INSERT_SORT 7
void ISort(int k[], int n)
{
    int i, j, temp;
    for( i=1; i < n; i++ )
    {
        if( k[i] < k[i-1] )
        {
            temp = k[i];
            for( j=i-1; k[j] > temp; j-- )
            {
                k[j+1] = k[j];
            }
            k[j+1] = temp;
        }
    }
}
void InsertSort(int k[], int low, int high)
{
    ISort(k+low, high-low+1);
}
void swap(int k[], int low, int high)
{
    int temp;
    temp = k[low];
    k[low] = k[high];
    k[high] = temp;
}
int Partition(int k[], int low, int high)
{
    int point;
    int m = low + (high-low)/2;
    if( k[low] > k[high] )
    {
        swap(k, low, high);
    }
    if( k[m] > k[high] )
    {
        swap(k, m, high);
    }
    if( k[m] > k[low] )
    {
        swap(k, m, low);
    }
    // 将low变成中间值
    point = k[low];
    while( low < high )
    {
        while( low < high && k[high] >= point )
        {
            high--;
        }
        k[low] = k[high];
        while( low < high && k[low] <= point )
        {
            low++;
        }
        k[high] = k[low];
    }
    k[low] = point;
}
void QSort(int k[], int low, int high)
{
    int point;
    if( high - low > MAX_LENGTH_INSERT_SORT )
    {
        point = Partition(k, low, high);  // 计算基准点，将小于基准点的数放在左边，大的放在右边
        QSort(k, low, point-1);
        QSort(k, point+1, high);
    }
    else
    {
        InsertSort(k, low, high);
    }
}   
void QuickSort(int k[], int n)
{
    QSort(k, 0, n-1);
} 
int main()
{
    int i;
    int a[10] = {5, 2, 6, 0, 3, 9, 1, 7, 4, 8};
    QuickSort(a, 10);
    printf("排序后的结果是： \n");
    for( i=0; i < 10; i++ )
    {
        printf("%d", a[i]);
    }
    printf("\n");
    return 0;
}

11.8.1.4 优化递归操作

• 尾递归
  
  • 如果一个函数中递归形式的调用出现在函数的末尾，我们称这个递归函数是尾递归的。
  • 当编译器检测到一个函数调用是尾递归的时候，它就覆盖当前的活跃记录，而不是在栈中去创建一个新的。编译器可以做到这点，因为递归调用是当前活跃期内最后一条待执行的语句，于是当这个调用返回时栈帧中并没有其他事情可以做，因此也就没有保存栈帧的必要了。通过覆盖当前的栈帧而不是在其之上重新添加一个，这样所使用的栈空间就大大缩减了，这使得实际运行效率会变得更高。
  • 因此，只要有可能，我们就需要将函数携程

#include <stdio.h>
#define MAX_LENGTH_INSERT_SORT 7
void ISort(int k[], int n)
{
    int i, j, temp;
    for( i=1; i < n; i++ )
    {
        if( k[i] < k[i-1] )
        {
            temp = k[i];
            for( j=i-1; k[j] > temp; j-- )
            {
                k[j+1] = k[j];
            }
            k[j+1] = temp;
        }
    }
}
void InsertSort(int k[], int low, int high)
{
    ISort(k+low, high-low+1);
}
void swap(int k[], int low, int high)
{
    int temp;
    temp = k[low];
    k[low] = k[high];
    k[high] = temp;
}
int Partition(int k[], int low, int high)
{
    int point;
    int m = low + (high-low)/2;
    if( k[low] > k[high] )
    {
        swap(k, low, high);
    }
    if( k[m] > k[high] )
    {
        swap(k, m, high);
    }
    if( k[m] > k[low] )
    {
        swap(k, m, low);
    }
    // 将low变成中间值
    point = k[low];
    while( low < high )
    {
        while( low < high && k[high] >= point )
        {
            high--;
        }
        k[low] = k[high];
        while( low < high && k[low] <= point )
        {
            low++;
        }
        k[high] = k[low];
    }
    k[low] = point;
}
void QSort(int k[], int low, int high)
{
    int point;
    if( high - low > MAX_LENGTH_INSERT_SORT )
    {
        while( low < high )
        {
            point = Partition(k, low, high);  // 计算基准点，将小于基准点的数放在左边，大的放在右边
            if( point-low < high-point )
            {
                QSort(k, low, point-1);
                low = point + 1;
            }
            else
            {
                QSort(k, point+1, high);
                high = point-1;
            }
        }           
    }
    else
    {
        InsertSort(k, low, high);
    }
}   
void QuickSort(int k[], int n)
{
    QSort(k, 0, n-1);
} 
int main()
{
    int i;
    int a[10] = {5, 2, 6, 0, 3, 9, 1, 7, 4, 8};
    QuickSort(a, 10);
    printf("排序后的结果是： \n");
    for( i=0; i < 10; i++ )
    {
        printf("%d", a[i]);
    }
    printf("\n");
    return 0;
}

11.9 总结回顾