排序的算法有很多, 冒泡, 选择, 直接插入, 鸡尾酒, 快排, 堆排......, 下文主将尽可能的介绍本人学过的所有排序 (会不断更新, 本人还在学习), 以从小到大为最终排序结果, C 为主要实现语言.
一, 冒泡排序 (Bubble Sort):
冒泡排序是一种简单的利用交换来完成排序的算法. 它重复地走访过要排序的数列, 一次比较两个元素, 如果他们的顺序错误就把他们交换过来. 走访数列的工作是重复地进行直到没有再需要交换, 也就是说该数列已经排序完成. 这个算法的名字由来是因为越小的元素会经由交换慢慢 "浮" 到数列的顶端.
冒泡算法的步骤:
比较相邻的元素. 如果前一个元素数比后一个元素大, 就交换它们两个.
对每一对相邻元素做同样的工作, 从开始 0 和 1 到结尾的 n-1 和 n. 所以, 最后的元素应该会是最大的数.
针对所有的元素重复以上的步骤, 除了最后一个.
持续每次对越来越少的元素重复上面的步骤, 直到没有任何一对数字需要比较.
下面是代码:
- void bubble_sort(int arr[], int len)
- {
- int i, j;
- for (i = 0; i <len - 1; i++) // 需要进行比较的轮数
- {
- for (j = 0; j < len - 1 - i; j++) // 每轮需要进行比较的次数,
- // 因为每一轮都有一个最大的数被放到了最后一个, 所以第 i 轮就有 i 个数不需要排序 (这里就存在优化的可能)
- if (arr[j]> arr[j + 1]) // 相邻的两个元素两两进行比较
- {
- arr[j] = arr[j] ^ arr[j+1];
- arr[j+1] = arr[j] ^ arr[j+1];
- arr[j] = arr[j] ^ arr[j+1]; // 交换
- }
- }
- }
- Bubble sort
冒泡排序的问题很明显, 举个例子
当数组元素为 1 2 3 9 4 5 6 7 8 时:
第一轮: 1 2 3 4 5 6 7 8 9;
第二轮: 1 2 3 4 5 6 7 8 9;
第三轮: 1 2 3 4 5 6 7 8 9;
至此我们可以看出在第一轮的时候数组就已经排好序了, 然而冒泡排序仍然在兢兢业业的工作 (真是好员工, 可惜效率低了点).
所以我们可尝试着优化一下, 在进行交换的时候标记一下, 当发数组遍历完都没有交换的情况, 也就证明已经排好序了, 我们的冒泡排序就可以提前下班了.
优化后的代码如下:
- void bubble_sort(int arr[], int len)
- {
- int i, j;
- for (i = 0; i <len - 1; i++) // 需要进行比较的轮数
- {
- int isSorted = 1; // 用 isSorted 进行标记, 默认其为已经完成排序, 也可以设置为 bool 型
- for (j = 0; j < len - 1 - i; j++) // 每轮需要进行比较的次数
- {
- // 因为每一轮都有一个最大的数被放到了最后一个, 所以第 i 轮就有 i 个数不需要排序
- if (arr[j]> arr[j + 1]) // 相邻的两个元素两两进行比较
- {
- isSorted = 0; // 进入交换后立刻置 0, 表示排序未完成
- arr[j] = arr[j] ^ arr[j+1];
- arr[j+1] = arr[j] ^ arr[j+1];
- arr[j] = arr[j] ^ arr[j+1]; // 交换
- }
- }
- if (isSorted) // 如果一直未交换就代表已经完成了排序, 也就是说可以提前下班了
- {
- break;
- }
- }
- }
- View Code
当我们继续测试后会发现冒泡排序的另一个问题
打个比方:
当数组为 33 54 32 21 56 67 78 89 时:
第二个 for 里
第一轮比较次数: 7
第二轮比较次数: 7
第三轮比较次数: 7
第四轮比较次数: 7
程序结束
第一轮的 7 次是怎么来的呢?
33 和 54 比较, 33 <54, 所以不变.
54 和 32 比较, 54> 32, 所以 54 和 32 换.
33 32 54 21 56 67 78 89
54 和 21 比较, 54> 21, 所以 54 和 21 换.
33 32 21 54 56 67 78 89
54 和 56 比较, 54 < 56, 不变.
56 和 67 比较, 56 <67, 不变.
67 和 78 比较, 67 < 78, 不变.
78 和 89 比较, 78 < 89, 不变.
第一轮至此结束.
第二轮的 6 次
33 和 32 比较, 33> 32, 所以 33 和 32 交换.
32 33 21 54 56 67 78 89
33 和 21 比较, 33> 21, 所以 33 和 21 交换.
32 21 33 54 56 67 78 89
33 和 54 比较, 33 <54, 所以不变.
54 和 56 比较, 54 < 56, 不变.
56 和 67 比较, 56 < 67, 不变.
67 和 78 比较, 67 < 78, 不变.
第二轮至此结束.
到这里基本就能看出问题了, 这个测试组, 从 56 往后都是有序的, 但是冒泡这位员工仍然一丝不苟的执行的他的任务.
从 56 往后的比较都是没有意义的, 所以我们应该考虑如何让程序识别已排好序的子列. 大家可以思考一下然后再往后看.
解决方法: 我们只需将要再最后一次元素进行交换的位置进行记录, 让第二 for 循环再这个范围内进行比较.
最终优化代码如下 (对我来说):
- void bubble_sort(int arr[], int len)
- {
- int i, j;
- int lastIndex, sortBorder; // 用来记录最后一次交换的下标和交换边界
- sortBorder = len -1; // 因为第一轮的时候 i = 0, 所以第一轮的 sortBorder == len - i - 1
- for (i = 0; i < len - 1; i++) // 需要进行比较的轮数
- {
- int isSorted = 1; // 用 isSorted 进行标记, 默认其为已经完成排序, 也可以设置为 bool 型
- for (j = 0; j < sortBorder; j++) // 每轮需要进行比较的次数
- {
- // 这里不在由 i 确定循环边界了, 这也是这次优化的核心
- if (arr[j]> arr[j + 1]) // 相邻的两个元素两两进行比较
- {
- isSorted = 0; // 进入交换后立刻置 0, 表示排序未完成
- lastIndex = j; // 记录下最后一次交换的位置
- arr[j] = arr[j] ^ arr[j+1];
- arr[j+1] = arr[j] ^ arr[j+1];
- arr[j] = arr[j] ^ arr[j+1]; // 交换
- }
- }
- sortBorder = lastIndex; // 讲最后一次交换的位置作为下次比较的边界
- if (isSorted) // 如果一直未交换就代表已经完成了排序, 也就是说可以提前下班了
- {
- break;
- }
- }
- }
- View Code
当然这也不最优的冒泡优化, 但是继续优化就涉及到另一个算法了, 所以目前对冒泡这个员工的整改就到这里
来源: http://www.bubuko.com/infodetail-2928404.html