排序

交换排序

nkul · 7月8日 · 2020年 · 214次已读

冒泡排序

从前往后,每次两两比较,将较大值往后移动。

void bubble(int a[],int n){
    for(int i=0;ii;j--){
            if(a[j]

一个小技巧,定义一个布尔值sorted,在第一次冒泡过程中,如果发现数组已经有序了(即没有发生交换),则在第二轮时直接跳出!

性质

  • 内部排序
  • 稳定
  • 适用于链表
  • 空间复杂度:o(1)
  • 时间复杂度:
    • 最坏:数组倒序,o(n^2)
    • 最好:数组顺序,o(n)

快速排序

注意:快排有很多实现方式,下面方式和图片无关!

数组[49,38,65,97,76,13,27,49,55,04]

1、第一趟:基准为49。从右开始找第一个比49小的(04),放到49处(04空出),从左找第一个大于49的65,放到04处;继续从右开始找,依此类推(右左交替)直到左右相遇,最后把基准放到相遇点;
2、递归处理相遇点左边、右边

int Partition(int a[],int l,int r){
    //哨兵
    int pivot = a[l];
    while(l=pivot) r--;
        a[l] = a[r];
        //从左往右找第一个比哨兵大的数,放到右指针处
        while (l

1、划分时,内部循环也要添加l

2、从右开始

3、划分有返回值

快排性质

  • 内部排序
  • 不稳定
  • 空间复杂度:
    • 最好:o(logn)
    • 最坏:o(n)
  • 时间复杂度:
    • 最好:o(logn)
    • 最坏:o(n^2)


0 条回应

必须 注册 为本站用户, 登录 后才可以发表评论!