第7章 常用学习算法数据结构2
- 归并排序（merge sort）
归并排序（merge sort）是一种基于分治思想的排序算法。它将数列分为若干个子序列，然后对子序列进行排序，最后合并已排序的子序列以获得完全有序的数列。归并排序的核心思想是利用归并操作将两个已排序的子序列合并成一个有序序列。
归并排序的基本步骤如下：
1 将数列分为两个长度相等的子序列。
2 对每个子序列进行递归地归并排序。
3 将两个已排序的子序列合并成一个有序序列。
以下是一个归并排序的示例实现（使用javascript）：
```javascript
function mergesort(arr) {
// 递归终止条件：子序列长度为1
if (arrlength ＜= 1) {
return arr;
}
// 分解数列：将数列分为两个长度相等的子序列
const mid = mathfloor(arrlength / 2);
const left = arrslice(0, mid);
const right = arrslice(mid);
// 递归地对子序列进行归并排序
const sortedleft = mergesort(left);
const sortedright = mergesort(right);
// 合并已排序的子序列
return merge(sortedleft, sortedright);
}
function merge(left, right) {
const merged = [];
let leftindex = 0;
let rightindex = 0;
// 比较左右子序列的首个元素，将较小者添加到合并后的数列
while (leftindex ＜ leftlength && rightindex ＜ rightlength) {
if (left[leftindex] ＜= right[rightindex]) {
mergedpush(left[leftindex]);
leftindex++;
} else {
mergedpush(right[rightindex]);
rightindex++;
}
}
// 将剩余元素添加到合并后的数列
while (leftindex ＜ leftlength) {
mergedpush(left[leftindex]);
leftindex++;
}
while (rightindex ＜ rightlength) {
mergedpush(right[rightindex]);
rightindex++;
}
return merged;
}
const arr = [64, 34, 25, 12, 22, 11, 90];
consolelog(mergesort(arr)); // 输出: [11, 12, 22, 25, 34, 64, 90]
```
归并排序的时间复杂度为o(nlogn)，在所有相同时间复杂度的排序算法中，其性能较好。归并排序在处理大数据集时具有稳定的性能，但在处理小规模数据集时，由于递归调用栈的开销，性能可能不如其他排序算法。
- 快速排序（quick sort）
快速排序（quick sort）是一种基于分治思想的排序算法。它将数列分为两个子序列，一个包含小于主元的元素，另一个包含大于主元的元素。然后递归地对子序列进行快速排序，最终将子序列合并成一个有序数列。
快速排序的基本步骤如下：
1 选择一个主元（pivot），通常选择数列的第一个元素。
2 将数列中小于主元的元素移到主元左边，大于主元的元素移到主元右边。这个过程称为分区（partition）操作。
3 对主元左边和右边的子序列递归地进行快速排序。
4 合并已排序的子序列以获得完全有序的数列。
以下是一个快速排序的示例实现（使用javascript）：
```javascript
function quicksort(arr) {
// 递归终止条件：子序列长度为1
if (arrlength ＜= 1) {
return arr;
}
const pivotindex = mathfloor(arrlength / 2);
const pivot = arrsplice(pivotindex, 1)[0];
const left = [];
const right = [];
for (let i = 0; i ＜ arrlength; i++) {
if (arr[i] ＜ pivot) {
leftpush(arr[i]);
} else {
rightpush(arr[i]);
}
}
return quicksort(left)concat([pivot], quicksort(right));
}
const arr = [64, 34, 25, 12, 22, 11, 90];
consolelog(quicksort(arr)); // 输出: [11, 12, 22, 25, 34, 64, 90]
```
快速排序的平均时间复杂度为o(nlogn)，在所有相同时间复杂度的排序算法中，其性能较好。快速排序在处理大数据集时具有稳定的性能，但在处理小规模数据集时，由于递归调用栈的开销，性能可能不如其他排序算法。
快速排序是一种原地排序算法，即它不需要额外的存储空间。然而，快速排序的性能受到分区策略的影响。在实际应用中，可以使用一些优化策略（如随机选取主元或改进分区算法）来提高快速排序的性能。