十大排序算法

大标 2022年3月16日18:51:11
评论
19

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;
}
 
2、选择排序
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);

  }

}

 

不稳定

 

 

 

  • 我的微信
  • 微信扫一扫
  • weinxin
  • 我的微信公众号
  • 微信扫一扫
  • weinxin
大标
  • 本文由 发表于 2022年3月16日18:51:11
  • 转载请务必保留本文链接:https://www.tanhuibiao.com/script/qita/5043.html
匿名

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: