排序

基本概念

定义

重新排列表中的元素，使其满足元素按照关键字有序的过程

排序算法稳定性：假设待排序表中，两个元素R1和R2，对应关键字Key1==Key2，在使用某种排序算法后，仍保持原先的相对顺序，则该排序算法稳定；否则不稳定。（算法是否稳定并不衡量排序算法的优劣，只是描述性质

根据数据元素是否完全在内存中，可以将排序算法分为内部排序和外部排序

并非所有排序都要基于元素之间的比较，例如基数排序

例题

对n个数进行基于比较的排序，需要进行至少「log(2, n!) 次关键字之间的比较

插入排序

基本思想：将每一个待排序元素插入前面已排序好的子序列，直到排序完成。

可以引申出：直接插入排序、折半插入排序和希尔排序

直接插入排序

算法流程：

  1. 找出L(i)在L[1…i-1]中的插入位置
  2. 进行插入

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// 逐个交换版本
void Insert_Sort1(int nums[], int len){
    for(int i=1;i<len;++i){
        // 将nums[i]插入前面排好的序列
        for(int j=i;j>0;--j){
            // 如果比前面的元素小，就前移
            if(nums[j-1]>nums[j]){
                std::swap(nums[j-1], nums[j]);
            }else{
                break;
            }
        }
    }
}
// 整体后挪版本
void Insert_Sort2(int nums[], int len){
    // 在nums[0]位置设置哨兵，存储当前处理的元素，在移动数组的过程中就不怕被覆盖
    for(int i=2;i<=len;++i){
        // 如果当前元素需要排序
        if(nums[i]<nums[i-1]){
            nums[0] = nums[i];  // 哨兵
        }
        // 插入位置后的序列往后面挪动
        int j=i-1;
        for(;nums[0]<nums[j];--j){
            nums[j+1] = nums[j];
        }
        nums[j+1] = nums[0];
    }
}

时间复杂度：O(n^2)

空间复杂度：O(1)

稳定性：稳定

适用性：适用于顺序存储和链式存储的线性表

折半插入排序

在查找插入位置的时候使用折半查找进行优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void Insert_Sort3(int nums[], int len){
    // 在nums[0]位置设置哨兵，存储当前处理的元素，在移动数组的过程中就不怕被覆盖
    for(int i=2;i<=len;++i){
        if(nums[i]<nums[i-1]){
            // 找第一个大于等于nums[i]的元素
            nums[0] = nums[i];  // 哨兵
            int left = 1, right = i-1;
            // 左闭右开 向下取整
            while(left < right){
                int mid = left+((right-left)>>1);
                if(nums[mid] < nums[i]){
                    ++left;
                }else{
                    --right;
                }
            }
            // 整体右移
            for(int j=i-1;j>=left;--j){
                nums[j+1] = nums[j];
            }
            nums[left] = nums[0];
        }
    }
}

时间O(n^2)

空间O(1)

稳定

希尔排序

希尔排序，又称缩小增量排序。

把相隔d增量的元素记录为一个子表，在各组内进行直接插入排序。不断缩小步长，直到步长为1，此时直接插入排序。因为有较好的局部有序性，所有可以很快得到结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void Shell_Sort(int nums[], int len){
    // nums[0]为暂存单元
    // dk为步长
    for(int dk=len/2;dk>0;dk/=2){
        for(int i=dk+1;i<=len;i++){
            // 如果需要排序
            if(nums[i]<nums[i-dk]){
                nums[0]=nums[i];
                int j=i-dk;
                // 寻找插入位置
                for(;j>0 && nums[0]<nums[j];j-=dk){
                    nums[j+dk] = nums[j];
                }
                nums[j+dk] = nums[0];
            }
        }
    }
}

时间复杂度：较难分析，n在某个特定区间内为O(n^1.3)，最坏时间复杂度为O(n^2)

空间复杂度：O(1)

不稳定

适用性：仅适用于线性表为顺序存储的情况

交换排序

包括冒泡排序和快速排序

冒泡排序

基本思想：从后往前（或者从前往后）两两比较相邻元素的值，若为逆序，则交换他们，知道序列比较完，称为一次冒泡，结果是最小的元素交换到待排序序列的第一个位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void Bubble_Sort(int nums[], int len){
    for(int i=0;i<len-1;++i){
        bool flag = false;      // 记录是否发生过交换
        for(int j=len-1;j>i;--j){
            // 冒泡
            if(nums[j]<nums[j-1]){
                std::swap(nums[j-1], nums[j]);
                if(!flag)   flag = true;
            }
        }
        // 没有发生过swap，说明已经有序
        if(!flag)    return;
    }
}

时间复杂度：O(n^2)

空间复杂度：O(1)

稳定

快速排序

思想：基于分治。

  1. 在待排序表中任意选取一个元素pivot，通过一趟排序，将待排序表分为独立的两部分L和R，L中所有元素小于pivot，R中所有元素大于pivot，
  2. 此时pivot位于有序数组的最终位置上
  3. 递归处理L和R。直到每部分内都只有一个元素

Partition过程

Partition将待排序表划分。快速排序的性能主要取决于此。

此处以《数据结构》王蔚敏版本的做法，以表中第一个元素作为枢轴pivot，进行划分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int partition(int nums[], int left, int right){
    int pivot = nums[left];
    while(left < right){
        // 将小于pivot的元素移到左边
        while(left<right && nums[right]>=pivot){
            --right;
        }
        nums[left] = nums[right];
        // 将大于pivot的元素移到右边
        while(left<right && nums[left]<=pivot){
            ++left;
        }
        nums[right] = nums[left];
    }
    nums[left] = pivot;
    return left;
}

类似荷兰国旗问题的partition

1
2
3
4
5
6
7
8
9
10
11
int partition(int nums[], int left, int right){
    int pivot = nums[left];     // 选取第一个元素作为枢轴
    int leftBoard = left-1;     // 处理好的左半边的边界
    for(int i=left;i<=right;++i){
        if(nums[i]<=pivot){
            std::swap(nums[i], nums[++leftBoard]);
        }
    }
    std::swap(nums[left], nums[leftBoard]); // 枢轴放到正确的位置上
    return leftBoard;
}

递归处理部分

1
2
3
4
5
6
7
8
9
void QuickSort(int nums[], int left, int right){
    // 表长大于1时才需要快排
    if(left < right){
        int pivotPos = partition(nums, left, right);
        // 递归处理左右子表
        QuickSort(nums, left, pivotPos-1);
        QuickSort(nums, pivotPos+1, right);
    }
}

空间复杂度：O(log(2, n)) 递归需要用栈

时间复杂度：O(log(2, n))

稳定性：不稳定

习题

  • 2/ 编写双向冒泡排序算法，在正反两个方向交替进行扫描：即第一趟把最大的关键字放在序列最后，第二趟把最小的关键字放在最前，如此往复

思路：用一个times变量控制扫描方向

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void _02_BiDirection_bubble_sort(int nums[], int len){
    int times = 1;
    // i j 记录待排序的序列两端
    int i = 0, j = len-1;
    while(i != j){
        // 正向冒泡
        if(times % 2 == 1){
            for(int k=i;k<j;++k){
                if(nums[k]>nums[k+1]){
                    std::swap(nums[k], nums[k+1]);
                }
            }
            --j;
        }
        // 反向冒泡
        else{
            for(int k=j;k>i;--k){
                if(nums[k]<nums[k-1]){
                    std::swap(nums[k], nums[k-1]);
                }
            }
            ++i;
        }
        ++ times;
    }
}
  • 3/ 线性表按顺序存储，每个元素是都不相同的整形，要求将所有奇数移动到所有偶数前面

思路：荷兰国旗问题的变种，将所有奇数移动就可以

1
2
3
4
5
6
7
8
void _03_func(int nums[], int len){
    int left = 0;   // 表示已经整理好的左边序列的末尾后一位
    for(int i=0;i<len;++i){
        if(nums[i] % 2 == 1){
            std::swap(nums[i], nums[left++]);
        }
    }
}
  • 5/ 在数组中找出第k小的元素

思路：先快排，然后直接取出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// partition
int partition(int nums[], int left, int right){
    int pivot = nums[left];
    while(left<right){
        while(left<right && nums[right]>=pivot){
            --right;
        }
        nums[left] = nums[right];
        while(left<right && nums[left]<=pivot){
            ++left;
        }
        nums[right] = nums[left];
    }
    nums[left] = pivot;
    return left;
}
// QuickSort
void QuickSort(int nums[], int left, int right){
    if(left<right){
        int pivotPos = partition(nums, left, right);
        QuickSort(nums, left, pivotPos-1);
        QuickSort(nums, pivotPos+1, right);
    }
}
// solution
int _05_find_k(int nums[], int len, int k){
    QuickSort(nums, 0, len-1);
    return nums[k];
}
  • 6/ 荷兰国旗问题：设有一个仅有红白蓝三种颜色的条块组成的序列，编写算法使序列按照红、白、蓝的顺序排好，即排成荷兰国旗图案

思路：

  1. 假设0代表红，1代表白，2代表蓝。
  2. 只要将0和2排到数组前面和后面，就完成题意
  3. 设置left表示左边排好序的边界，right表示右边的边界。进行一遍扫描，交换
1
2
3
4
5
6
7
8
9
10
11
12
13
void _05_Holland_Flag(int nums[], int len){
    int left = -1, right = len;     // 两个边界
    int index = 0;      // 扫描数组变量
    while(index < right){
        if(nums[index] == 0){
            std::swap(nums[index++], nums[++left]);
        }else if(nums[index] == 2){
            std::swap(nums[index], nums[--right]);
        }else{
            ++index;
        }
    }
}
  • 6/ （2016统考真题）已知n(n>=2)个正整数构成的集合A，将其划分为两个不相交子集A1和A2，元素个数为n1和n2，子集内元素和为S1和S2，设计一个高效的划分算法，满足|n1-n2|最小并且|S1-S2|最大

思路：贪心思想，|n1-n2|最小，要求平分；|S1-S2|最大，要求A1内元素都小，A2内元素都大。因此，类似快排，选取一个枢轴，他应当排序后位于数组中间

  1. 选取一个枢轴 将其放到正确位置
  2. 正确位置为len/2-1。
  3. 如果枢轴位置刚好等于len/2-1，那就计算答案
  4. 如果小于len/2-1，则划分右半边；否则划分左半边，更改边界即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
int _06_func(int nums[], int len){
    int left = 0, right =len-1, pos = len/2;
    bool flag = true;
    while(flag){
        int pivot = nums[left];
        while(left < right){
            while(left < right && nums[right] >= pivot){
                -- right;
            }
            nums[left] = nums[right];
            while(left < right && nums[left] <= pivot){
                ++ left;
            }
            nums[right] = nums[left];
        }
        nums[left] = pivot;
        if(left == pos-1)   flag = false;       // 如果pivot位于pos，划分成功
        else{
            if(left < pos-1){
                left += 1;
                right = len-1;
            }else{
                right -= 1;
                left = 0;
            }
        }
    }
    int sum1 = 0, sum2 = 0;
    for(int i=0;i<pos;++i){
        sum1 += nums[i];
    }
    for(int i=pos;i<len;++i){
        sum2 += nums[i];
    }
    return sum2-sum1;
}

选择排序

基本思想：每一趟排序，在后面的待排序序列中找到一个最小值，放到排好序序列的后面。

简单选择排序

每一趟在L[i…n]中找到最小值，和L(i)进行交换

1
2
3
4
5
6
7
8
9
10
11
12
void Select_Sort(int nums[], int len){
    for(int i=0;i<len-1;++i){
        int minPos=i;   // 最小值所在的下标
        for(int j=i+1;j<len;++j){
            if(nums[j] < nums[minPos]){ // 更新最小值
                minPos = j;
            }
        }
        if(minPos != i)
            std::swap(nums[i], nums[minPos]);
    }
}

时间复杂度：O(n^2)

空间复杂度：O(1)

稳定性：不稳定

堆排序

堆的定义

n个关键字序列L[1…n]满足以下条件可以成为堆

  1. L(i)>=L(2i) && L(i)>=L(2i+1) 或者
  2. L(i)<=L(2i) && L(i)<=L(2i+1)

满足条件1称为大根（顶）堆，满足条件2称为小根（顶）堆

堆可以视为一棵完全二叉树

以大顶堆实现为例，排序结果为从小到大。区别于王道考研书，这里数组下标从0开始计算

堆化

堆化是自上而下的

对于每一个节点，比较自己和孩子中较大的那个，不断下沉

1
2
3
4
5
6
7
8
9
10
11
12
13
void heapify(int nums[], int len, int k){
    for(int i=2*k+1;i<len;i=i*2+1){
        // 右孩子存在并且比左孩子大，则选取左孩子
        if(i+1 < len && nums[i+1] > nums[i]){
            i = i+1;
        }
        if(nums[k] > nums[i])   break;  //
        else{
            std::swap(nums[k], nums[i]);
            k = i;
        }
    }
}

建立堆

建立堆是自下而上的

对于每一个节点，比较自己和父节点，不满足堆的性质则进行交换

1
2
3
4
5
void BuildHeap(int nums[], int len){
    for(int i=(len-2)/2;i>=0;--i){
        heapify(nums, len, i);
    }
}

堆排序

堆排序则是：

  1. 建立堆
  2. 每次取出堆顶元素（待排序序列中的最大值），与后面排序完成的序列前一位进行交换。然后对新的堆顶元素堆化
  3. 当堆只有一个元素时，堆排序完成
1
2
3
4
5
6
7
void Heap_Sort(int nums[], int len){
    BuildHeap(nums, len);
    for(int i=len-1;i>0;--i){
        std::swap(nums[0], nums[i]);
        heapify(nums, i, 0);    // 调整新的堆顶
    }
}

时间复杂度：O(n*log(2, n))

空间复杂度：O(1)

稳定性：不稳定

堆排序适用于关键字较多的情况，例如10000个数据中取最小的100个，可以用大小为100的堆实现

归并排序和基数排序

归并排序

不同于之前的基于比较、选择等排序，归并排序的基本思想是：将两个或两个以上的有序表组合成一个新的有序表。

Merge 操作

Merge 将两个表合并成一个有序表，需要借助一个辅助数组来完成。双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void Merge(int nums[], int left, int mid, int right){
    int helper[right-left+1];   // 辅助数组
    int index1 = left, index2 = mid+1, index3 = 0;  // 三指针
    while(index1 <= mid && index2 <=right){
        helper[index3++] = nums[index1]<nums[index2] ? nums[index1++] : nums[index2++];
    }
    // 剩余的表直接复制
    while(index1 <= mid)    helper[index3++] = nums[index1++];
    while(index2 <= right)    helper[index3++] = nums[index2++];
    // 辅助数组搬到原数组
    for(int i=0;i<right-left+1;++i){
        nums[left+i] = helper[i];
    }
}

MergeSort 操作

MergeSort递归做法，类似树的后序遍历。

1
2
3
4
5
6
7
8
void MergeSort(int nums[], int left, int right){
    if(left < right){
        int mid = left+((right-left)>>1);
        MergeSort(nums, left, mid);         // 让左边有序
        MergeSort(nums, mid+1, right);      // 让右边有序
        Merge(nums, left, mid, right);      // 合并成一个大的有序
    }
}

时间复杂度：O(n*log(2, n))

空间复杂度：O(n) 来自辅助数组和递归函数栈

稳定性：稳定

基数排序

赏

谢谢你请我吃糖果

支付宝
微信

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

一定要赢