https://www.cnblogs.com/onepixel/articles/7674659.html
- 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
- 不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
- 时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
- 空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。
1、冒泡排序
function bubbleSort(arr) {
var len = arr.length;
for (var i = 0; i < len - 1; i++) {
for (var j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j+1]) { // 相邻元素两两对比
var temp = arr[j+1]; // 元素交换
arr[j+1] = arr[j];
arr[j] = temp;
}
}
}
return arr;
}function selectionSort(arr) {
var len = arr.length;
var minIndex, temp;
for (var i = 0; i < len - 1; i++) {
minIndex = i;
for (var j = i + 1; j < len; j++) {
if (arr[j] < arr[minIndex]) { // 寻找最小的数
minIndex = j; // 将最小数的索引保存
}
}
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
return arr;
} 算法分析
表现最稳定的排序算法之一，因为无论什么数据进去都是O(n2)的时间复杂度，所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。
不稳定
6 7 6 2 8
3、插入排序
function insertionSort(arr) {
var len = arr.length;
var preIndex, current;
for (var i = 1; i < len; i++) {
preIndex = i - 1;
current = arr[i];
while (preIndex >= 0 && arr[preIndex] > current) {
arr[preIndex + 1] = arr[preIndex];
preIndex--;
}
arr[preIndex + 1] = current;
}
return arr;
}算法分析
插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
4、希尔排序
function shellSort(arr) { var len = arr.length;
for (var gap = Math.floor(len / 2); gap > 0; gap = Math.floor(gap / 2)) {
// 注意：这里和动图演示的不一样，动图是分组执行，实际操作是多个分组交替执行
for (var i = gap; i < len; i++) {
var j = i;
var current = arr[i];
while (j - gap >= 0 && current < arr[j - gap]) {
arr[j] = arr[j - gap];
j = j - gap;
}
arr[j] = current;
}
}
return arr;
}不稳定
3 5 10 8 7 2 8 1 20 6
ga p为2时， 3 10 7 8 20 为一组 5 8 2 1 6 为一组
第二组的8（第一个8）回放在最后的位置
5、归并排序
function mergeSort(arr) {
var len = arr.length;
if (len < 2) {
return arr;
}
var middle = Math.floor(len / 2),
left = arr.slice(0, middle),
right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}function merge(left, right) { var result = [];
while (left.length>0 && right.length>0) {
if (left[0] <= right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}
while (left.length)
result.push(left.shift());
while (right.length)
result.push(right.shift());
return result;
}算法分析
归并排序是一种稳定的排序方法。和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(nlogn）的时间复杂度。代价是需要额外的内存空间。
6、快速排序
int partition(int arr[], int low, int high)
{
int pivot = arr[high];
int i = low;
for (int j = low; j < high; j++)
{
if (arr[j] < pivot)
{
swap(&arr[j], &arr[i++]);
}
}
swap(&arr[high], &arr[i]);
return i;
}
void qsort(int arr[], int left, int right)
{
int mid = partition(arr, left, right);
qsort(arr, left, mid - 1);
qsort(arr, mid + 1, right);
}
int quick_sort(int arr[], int len)
{
qsort(arr, 0, len - 1);
}
7、堆排序
维护堆（大顶堆）
void heapify(int arr[], int n , int i)
{
int largest = i;
int lson = i* 2 + 1;
int rson = i * 2 + 2;
if (lson < n && arr[largest] < arr[lson])
{
largest = lson;
}
if (rson < n && arr[largest] < arr[rson])
{
largest = rson;
}
if (largest != i)
{
swap(&arr[largest], &arr[i]);
heapify(arr, n, largest);
}
}
堆排序入口
void heap_sort(arr, int n)
{
int i;
建堆
for (i = n / 2 - 1; i > = 0; i--)
{
heapify(arr, n, i);
}
排序
for (i = n - 1; i > 0; i--)
{
swap(&arr[0], &arr[i]);
heapify(arr, i, 0);
}
}
不稳定
- 我的微信
- 微信扫一扫
-
- 我的微信公众号
- 微信扫一扫
-
评论