常见排序算法比如:
- 冒泡排序(属于交换排序)
- 快速排序(属于交换排序)
- 直接插入排序(属于插入排序)
- 希尔排序(属于插入排序)
- 简单选择排序(属于选择排序)
- 堆排序(属于选择排序)
- 归并排序
- 基数排序
下面通过 JavaScript 实现各个排序算法。
冒泡排序
冒泡排序应该是印象中接触最早的排序算法。冒泡算法核心是顺序比较相邻的两个元素,在升序排列下,如果元素 i 大于 元素 i + 1,则交换两者,第一轮比较到最后一个元素,第二轮比较到倒数第二个元素。直到只剩下第一个元素,比较完毕。
中间有一个优化是,如果某轮比较没有进行交换,则认为数组已经有序,不需要进行下一轮比较。
另一个“改进”版本——双向冒泡,为了减少来回的次数。但实际并没有减少比较次数,反而申请了更多的内存空间。
function sortBubble(array) { var i, j = array.length - 1, tmp, no_change; while (j > 0) { no_change = true; for (i = 0; i < j; i++) { if (array[i] > array[i + 1]) { tmp = array[i]; array[i] = array[i + 1]; array[i + 1] = tmp; no_change = false; } } if (no_change) { break; } } } var ar_score = [10, 9, 8, 7, 6]; sortBubble(ar_score);
快速排序
快速排序通过设置哨兵,把小于和大于哨兵的数组元素分别组织为数组,再通过递归对两个数组进行快速排序,直到每个数组不能分解(只有一个数组元素)。
<script type="text/javascript"> function sortQuick(array) { var i = 0, j = array.length - 1, index = 0, guard = array[index]; var ar_left, ar_right; while (j > i) { while (j > index) { if (array[j] < guard) { array[index] = array[j]; array[j] = guard; index = j; break; } j--; } while (i < index) { if (array[i] > guard) { array[index] = array[i]; array[i] = guard; index = i; break; } i++; } } if (i > 0) { ar_left = array.slice(0, i); sortQuick(ar_left); array.splice.apply(array, [0, i].concat(ar_left)); } if (j < array.length - 1) { j++; ar_right = array.slice(j); sortQuick(ar_right); array.splice.apply(array, [j, array.length - j].concat(ar_right)); } } var ar_score = [10, 9, 8, 7, 6]; sortQuick(ar_score); </script>
[10, 9, 8, 7, 6] 交换步骤
- 第一次排序 [6, 9, 8, 7, 10]
- 分拆为 [6, 9, 8, 7]、[10], 左侧数组在进行快速排序、右侧数组不需要进行排序
- 第二次排序 [6, 9, 8, 7] 、[10], 分拆为 [6]、[9, 8, 7]、[10]
- 第三次排序 [6]、[7, 8, 9]、[10]
- 第四次排序 [6]、[7, 8], [9], [10]
- 第五次排序 [6]、[7], [8], [9]、[10]
- 拼装返回的数组列表得到 [6, 7, 8, 9, 10]
直接插入排序
插入排序是在实际生活中使用得比较早的排序,比如试卷评分,把试卷按照分数高低排序。
插入排序通过设置有序数组,从后续元素中依次比较元素与有序数组中元素的顺序,从而插入到指定位置,最终形成有序数组。
- 设置 a[0] 是一个有序数组,无序数组从 a[1…length-1]。length 为数组长度,假定 i = 1
- 将 a[i] 插入到有序数组 a[0…i-1]
- 将 i++,如果 i 小于 length 则重复第二步
- 排序结束
<script type="text/javascript"> function sortInsert(array) { var i = 1, j, k, length = array.length, tmp; if (!(length > 1)) { return; } do { for (j = i - 1; j > -1; j--) { if (array[j] < array[i]) { break; } } if (j != i - 1) { tmp = array[i]; for (k = i - 1; k > j; k--) { array[k + 1] = array[k]; } array[k + 1] = tmp; } i++; } while (i < length); } var ar_score = [10, 9, 8, 7, 6]; sortInsert(ar_score); </script>
[10, 9, 8, 7, 6] 插入步骤
- 第1次排序,设置有序数组 [10],插入数组元素 9,得到 [9, 10]、[8, 7, 6]
- 第2次排序,有序数组 [9, 10],插入数组元素 8,得到 [8, 9, 10]、[7, 6]
- 第3次排序,有序数组 [8, 9, 10],插入数组元素 7,得到 [7, 8, 9, 10]、[6]
- 第4次排序,有序数组 [7, 8, 9, 10],插入数组元素 6,得到 [6, 7, 8, 9, 10]
直接插入排序在第二步插入时,需要用到查询,上述代码的一个改进点是使用二分查找,降低时间复杂度。
希尔排序
希尔排序
简单选择排序
简单选择排序
堆排序
堆排序
归并排序
归并排序
基数排序
基数排序