第一章 常规排序算法

• 第一章 常规排序算法
  • 一、排序的基本概念
    • 1. 排序
    • 2. 内部排序与外部排序
    • 3. 排序的稳定性
  • 二、冒泡排序
    • 1. 算法思想
    • 2. 冒泡排序图示
    • 3. C 语言实现
    • 4. Java 语言实现
    • 5. 算法分析
      • 1> 时间复杂度
      • 2> 空间复杂度
      • 3> 算法稳定性
  • 三、简单选择排序
    • 1. 算法思想
    • 2. 简单选择排序图示
    • 3. C 语言实现
    • 4. Java 语言实现
    • 5. 算法分析
      • 1> 时间复杂度
      • 2> 空间复杂度
      • 3> 算法稳定性
  • 四、直接插入排序
    • 1. 算法思想
    • 2. 直接插入排序图示：
    • 3. C 语言实现
    • 4. Java 语言实现
    • 5. 算法分析
      • 1> 时间复杂度
      • 2> 空间复杂度
      • 3> 算法稳定性
  • 五、希尔排序
    • 1. 直接插入排序的特点：
    • 2. 希尔排序算法思想：
    • 3. 希尔排序图示
    • 4. C 语言实现
    • 5. Java 语言实现
    • 6. 算法分析
      • 1> 时间复杂度
      • 2> 空间复杂度
      • 3> 算法稳定性
  • 六、参考资料

一、排序的基本概念

1. 排序

排序： 将一个数据元素的任意序列，重新排列成一个按关键字有序的序列。

2. 内部排序与外部排序

内部排序： 整个排序过程完全在内存中进行。
外部排序： 待排序记录数据量太大，内存无法容纳全部数据，排序需要借助外部存储设备才能完成。

3. 排序的稳定性

排序算法的稳定性： 如果原始序列中两个关键字相等的数据在排序后仍然保持排序前的顺序，我们称这样的排序算法是稳定的。

二、冒泡排序

1. 算法思想

1. 对 N 个元素进行冒泡排序，需进行 N - 1 趟排序过程；
2. 每趟排序，依次比较两个相邻元素，如果前者比后者大，则交换；否则，不交换，直到将当前最大值交换到本趟排序的最后。

2. 冒泡排序图示

冒泡排序

3. C 语言实现

void    BubbleSort(int r[], int n)
{
    int i = 0, j = 0, tmp = 0;
    // 外层循环：进行一趟排序，将当前最大值交换到最后
    for(i = 0; i < n - 1; i++)
    {  // 依次比较两个相邻元素，如果前者比后者大，则交换
        for(j = 0; j < n - 1 - i; j++)
        {
            if(r[j] > r[j + 1])
            {
                tmp = r[j];
                r[j] = r[j + 1];
                r[j + 1] = tmp;
            }
        }
    }
}

4. Java 语言实现

public void bubbleSort(int[] a) {
  for (int i = 0; i < a.length - 1; i++) {
    for (int j = 0; j < a.length - i - 1; j++) {
      if (a[j] > a[j + 1]) {
        int tmp = a[j];
        a[j] = a[j + 1];
        a[j + 1] = tmp;
      }
    }
  }
}

5. 算法分析

1> 时间复杂度

由以上代码可知：内层循环的迭代次数为：n(n-1)/2；
可见冒泡排序的时间复杂度为：O(n^2)

2> 空间复杂度

冒泡排序只额外申请了一个临时空间 tmp，用于交换两个变量；所以，空间复杂度为：O(1)

3> 算法稳定性

冒泡排序是 稳定的。
我们简单说明一下，

1. 首先，冒泡排序每次交换的是相邻两个元素；
2. 其次，只有当 a[j] > a[j + 1] 时才交换，如果 a[j] == a[j + 1] 时不进行交换，所以，相等的数据仍然保持原始的顺序。

三、简单选择排序

1. 算法思想

1. 首先，查找 N 个元素中的最小值，并将其和第一元素进行交换；
2. 然后，在剩下的 N - 1 个元素中找到最小值，并交换的第二个元素；
3. 以此类推，共进行 N - 1 趟查找，直到整个序列有序。

2. 简单选择排序图示

简单选择排序

3. C 语言实现

void    SelectionSort(int r[], int n)
{
    int i = 0, j = 0, min = 0, tmp = 0;
    for(i = 0; i < n - 1; i++)
    {
        min = i;
        for(j = i + 1; j < n; j++)
        {
            if(r[min] > r[j])
            {
                min = j;
            }
        }
        if(min != i)
        {
            tmp = r[min];
            r[min] = r[i];
            r[i] = tmp;
        }
    }
}

4. Java 语言实现

public void selectionSort(int[] a) {
  for (int i = 0; i < a.length - 1; i++) {
    int min = a[i];
    for (int j = i + 1; j < a.length; j++) {
      if (a[min] > a[j]) {
        min = j;
      }
    }
    if (min != i) {
      int tmp = a[min];
      a[min] = a[i];
      a[i] = tmp;
    }
  }
}

5. 算法分析

1> 时间复杂度

由以上代码可知：内层循环的迭代次数为：n(n-1)/2；
可见简单选择排序的时间复杂度为：O(n^2)

2> 空间复杂度

简单选择排序只只额外申请了两个临时空间 tmp 和 min，一个用于交换两个变量，一个用于记录当前最小值的下标。空间复杂度为：O(1)

3> 算法稳定性

简单排序算法是 不稳定的。
我们举一个例子。对于序列：*5, 3, 8, 5, 4, 2，第一趟排序时，会交换：5 和 2；这样，5 和 5 的顺序就颠倒了。

四、直接插入排序

1. 算法思想

1. 将第一个元素看做是一个只有一个元素的有序序列；
2. 把第二个元素插入到有序序列中去，这样，就构造了包含 2 个元素的有序序列；
3. 依次把第 3,4,5... 个元素插入先前的有序序列，最终使得整个序列有序。

2. 直接插入排序图示：

直接插入排序

3. C 语言实现

void    InsertSort(int r[], int n)
{
    int i = 0, j = 0, tmp = 0;
    printf("直接插入排序：");
    for(i = 1; i < n; i++)
    {
        tmp = r[i];
        for(j = i - 1; j >= 0 && tmp < r[j]; j--)
        {
            r[j + 1] = r[j];
        }
        r[j + 1] = tmp;
    }
}

4. Java 语言实现

public void insertSort(int[] a) {
  for (int i = 1; i < a.length; i++) {
    int tmp = a[i];
    int j = 0;
    for (j = i - 1; j >= 0 && tmp < a[j]; j--) {
      a[j + 1] = a[j];
    }
    a[j + 1] = tmp;
  }
}

5. 算法分析

1> 时间复杂度

由以上代码可知：内层循环在最坏情况下的迭代次数为：n(n-1)/2；
平均情况下直接插入排序的时间复杂度为：O(n^2)
但是，从前面的图示我们可以看到，直接插入排序的比较和交换次数明显比前述算法少很多，因此，比前述算法都快。

2> 空间复杂度

排序只额外申请了一个临时空间 tmp，用于交换两个变量；所以，空间复杂度为：O(1)

3> 算法稳定性

直接插入排序算法是 稳定的。
我们简单说明一下，

1. 首先，直接插入排序每次移动的是相邻两个元素；
2. 其次，只有当 tmp > a[j] 时才移动，如果 tmp == a[j] 时不进行交换，所以，相等的数据仍然保持原始的顺序。

五、希尔排序

希尔排序(Shell Sort) 是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。

1. 直接插入排序的特点：

1. 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。
2. 插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。

2. 希尔排序算法思想：

1. 先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；
2. 然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量
   dt=1(dt < dt-1 < … < d2 < d1)，即所有记录放在同一组中进行直接插入排序为止。
3. 方法本质上是一种分组插入方法

3. 希尔排序图示

希尔排序

4. C 语言实现

void    ShellSort(int r[], int n)
{
    int i = 0, j = 0, delta = 0, tmp = 0;
    // 增量从 n/2 开始，每次缩小一半，直到等于 1
    for(delta = n / 2; delta > 0; delta /= 2)
    {
        for(i = delta; i < n; i++)
        {
            tmp = r[i];
            for(j = i - delta; j >= 0 && tmp < r[j]; j -= delta)
            {
                r[j + delta] = r[j];
            }
            r[j + delta] = tmp;
        }
    }
}

5. Java 语言实现

public void shellSort(int[] a) {
  for (int delta = a.length / 2; delta > 0; delta /= 2) {
    for (int i = delta; i < a.length; i++) {
      int tmp = a[i];
      int j = 0;
      for (j = i - delta; j >= 0 && tmp < a[j]; j -= delta) {
        a[j + delta] = a[j];
      }
      a[j + delta] = tmp;
    }
  }
}

6. 算法分析

1> 时间复杂度

希尔排序的时间复杂度与选中的 增量d 有关的，分析希尔排序的时间复杂度比较麻烦；这里只给出结论：

• 在最好情况下，时间复杂度为：O(n^{1.3})（元素已经排序好顺序）
• 在最坏情况下，时间复杂度为：O(n^2)。
• 虽然，平均情况下时间复杂度为：O(n^2)，但是，较相同时间复杂度的其他算法而言，希尔排序相对是最好的。

2> 空间复杂度

希尔排序只额外申请了一个临时空间 tmp，用于交换两个变量。空间复杂度为：O(1)

3> 算法稳定性

希尔排序算法是 不稳定的。
我们举一个例子。对于序列：*5, 5, 8, 3, 4, 2，在 delta = 2 时，*5 和 5 的顺序会颠倒。根本原因是希尔排序每次移动元素时是跳跃移动的。

六、参考资料

1. 算法动画：http://jsdo.it/norahiko/oxIy/fullscreen