排序¶

1 选择排序¶

2 冒泡排序¶

2.1 定义¶

冒泡排序是一种算法，用于比较相邻元素，并在相邻元素未按预期顺序进行交换时交换它们的位置。顺序可以是升序或降序。

这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

2.2 气泡排序工作步骤¶

从第一个索引开始，比较元素 1 和 2，位置不对则进行交换，直到最后一个元素。这样保证最后一个元素是最大元素，我们称为已排序元素

第 1 次排序

跟之前一样，直到最后一个未排序元素。

第 2,3,4 次排序

2.3 程序¶

void bubbleSort(int array[], int size)
{
  for (int step = 0; step < size - 1; ++step)
  {
    for (int i = 0; i < size - step - 1; ++i)
    {
      if (array[i] > array[i + 1])// 升序，降序反过来
      {
        int temp = array[i];
        array[i] = array[i + 1];
        array[i + 1] = temp;
      }
    }
  }
}

int main()
{
  int data[] = {-2, 45, 0, 11, -9};
  int size = sizeof(data) / sizeof(data[0]);
  bubbleSort(data, size);
}

2.4 算法优化¶

上边工作步骤可以感觉到，如果顺序已经排好，还要进行所有比较。
我们设置信号量==swap==，如果本次没有发生排序，则直接结束。

2.5 优化程序¶

void bubbleSort(int array[], int size)
{
for (int step = 0; step < size - 1; ++step)
  {
    int swapped = 0;
    for (int i = 0; i < size - step - 1; ++i)
    {
      if (array[i] > array[i + 1])
      {
        int temp = array[i];
        array[i] = array[i + 1];
        array[i + 1] = temp;
        swapped++;
      }
    }
    if (swapped == 0)
      break;
  }
}

int main()
{
  int data[] = {-2, 45, 0, 11, -9};
  int size = sizeof(data) / sizeof(data[0]);
  bubbleSort(data, size);
}

2.6 复杂度¶

迭代	比较次数
第 1 次迭代	n-1
第 2 次迭代	n-2
第 3 次迭代	n-3
...	...
第 n 次迭代	1

总次数 = (n-1) + (n-2) + (n-3) +.....+ 1 = n (n-1)/2 近似 n²

2.7 应用¶

数据已经是快排好的

3 插入排序¶

4 快速排序¶

5 gui归并排序¶

6 堆排序¶

7 桶排序¶

将数据分配到固定数量的桶中，每个桶内的数据独立排序，最后将桶内的数据合并得到有序序列

适用于数据均匀
适用于已知数据范围
适用于数据量过大，无法一次加载到内存中
适用于实时系统，数据不断添加且需要快速排序和处理，新数据可以快速分配到桶中

8 计数排序¶

遍历数组nums，找出最大的数m，创建长度为m+1的辅助数组 counter
借助counter同级nums中各数字出现的次数
counter索引本身有序，每个数出现次数也记录好了，出现填入nums

桶排序的一个特例，只能用于整数数组。适用于数据量大且数据范围有限，通过预处理将数据转换为正整数。

9 基数排序¶

逐位进行计数排序，要求数据必须能表示为固定位数的数字。