11086 排序问题再探讨

题型: 编程题 语言: G++;GCC;VC;JAVA

Description

此题以程序填空的形式进行，请将下列程序框架复制到本机，并按下面要求填充完整后再用g++编译器提交，
在不改变程序框架情况下，可以自由添加所需的函数和变量，或修改合适的函数参数。
1，请改写一个"递归"的插入排序，排序a[0…n-1]，先递归的排序a[0…n-2]，然后再将a[n-1]插入到已排序
的a[0…n-2]中去。
2，自然合并排序，书上2.7节最后介绍的算法，请实现它。
3，快速排序，选择"中位数"作为轴值然后进行左右段分区，请实现它。

#include
#include “stdlib.h”
using namespace std;

void RecurInsertionSort(int p, int q) //对a[p…q]的递归插入排序，参数可根据自己需要修改。
{
……
}

void NaturalMergeSort(int n) //对n个元素的自然合并排序，参数可根据自己需要修改。
{
……
}

//以a[x]为基准元素划分a[p…q]，返回左右分区调整后的基准下标. 书上2.8节有，稍稍修改。
int Partition(int x, int p, int q) //参数和返回值可根据自己需要修改。
{
……
}

int RandomizedSelect(int p, int q, int k) //用任意选轴值的快速选择算法，返回a[p…q]的第k小元素的下标。
{
……
}

int median(int p, int q) //挑出a[p…q]的中位数,并返回中位数下标，参数和返回值可根据自己需要修改。
{
return RandomizedSelect(p, q, p+q/2);
}

void QuickSort(int p,int q) //参数可根据自己需要修改。
{
if(p>=q)return;
int x = median(p, q);
int i = Partition(x,p,q);
QuickSort(p,i-1); //递归
QuickSort(i+1,q);
}

int main()
{
int i,n;
cin >> n;

//递归插入排序 for(i=0;i<n;i++) { cin >> a[i]; } RecurInsertionSort(0,n-1); cout << "Insert sort: "; for(i=0;i<n;i++) { cout << a[i] << ' '; } //自然合并排序 for(i=0;i<n;i++) { cin >> a[i]; } NaturalMergeSort(n); cout << "\nNatural merge sort: "; for(i=0;i<n;i++) { cout << a[i] << ' '; } //快速排序 for(i=0;i<n;i++) { cin >> a[i]; } QuickSort(0, n-1); cout << "\nQuick sort: "; for(i=0;i<n;i++) { cout << a[i] << ' '; } return 0; 

}

输入格式

第一行：n，表示n个元素待排序。n不超过10000个。
第二行：n个数的序列，用来做递归的插入排序；
第三行：n个数的序列，用来做自然合并排序；
第四行：n个数的序列，用来做快速排序。

注意：第二、三、四行之间无联系，可能相同也可能不相同。

输出格式

三行，分别为三种排序算法排序后输出。
注意前面有“Insert sort:”或“Natural merge sort:”或“Quick sort:”等输出前缀，格式以
上文程序为准。

输入样例

9
3 5 2 1 7 8 1 5 9
8 5 2 1 7 3 1 5 9
5 9 2 1 7 8 1 3 5

输出样例

Insert sort: 1 1 2 3 5 5 7 8 9
Natural merge sort: 1 1 2 3 5 5 7 8 9
Quick sort: 1 1 2 3 5 5 7 8 9

讯享网

解题思路

1. 插入排序

原理：通过构建有序数列，把未排列数据，通过扫描，插入到有序数列的合适位置

插入排序的基本思想：每一趟将一个待排序的记录，按其关键字的大小插入到已经排好序的一组记录的适当位置上，直到所有的待排序记录全部插入为止。

注意：递归实现最重要的是要明确入口和出口，以及入口和出口的位置，否则很难调试出来。

算法流程：

1. 确定递归边界，当要排序的区间长度为1（即 q == 0）时，结束递归
2. 每次递归时，先对该区间前面的部分进行递归，保证前面都有序后，再将 a[q] 元素插入到前面的区间，即先 RecurInsertionSort(p, q - 1); //对前面K-1个数进行排序
3. 开始将 a[q] 元素插入到前面的区间，由于前面已经是有序区间，所以从后往前遍历，遍历到 a[q] 元素适合的插入位置即可

更多注释可查看下方的完整代码中，有助于理解

代码如下

讯享网void RecurInsertionSort(int p, int q) //对a[p…q]的递归插入排序，参数可根据自己需要修改。 { 
    if(q == 0) return; RecurInsertionSort(p, q - 1); //对前面K-1个数进行排序 int temp = a[q]; // 要插入到前面的元素，即数组最尾部元素 int r = q - 1; // 定义r指针从后往前寻找 temp 的插入位置 while(r >= 0 && temp < a[r]) { 
    // 元素纷纷往后移一位 a[r + 1] = a[r]; r--; } a[r + 1] = temp; // 找到位置后，插入即可 } 

2. 自然合并排序

即归并排序

原理：

1. 通过使用分治的算法，将列表划分为每次迭代中大约一半大小的子列表，直到每个子列表只有一个元素。
2. 重复合并每个子列表以创建排序列表。它将一直运行，直到我们只有一个排序列表。这将是排序列表。

分治过程如下

算法流程：

1. 确定递归边界，当区间长度只有1，结束递归，即 l >= r 时
2. 每次递归时，先找出区间中点，然后对左右两部分区间继续递归
3. 第二步会得到左右两部分都为有序数组的结果，然后再将这两部分有序数组进行合并即可

更多注释可查看下方的完整代码中，有助于理解

代码如下

void NaturalMergeSort(int l, int r) //对n个元素的自然合并排序，参数可根据自己需要修改。 { 
    int mid = (l + r) / 2; if(l < r) { 
    NaturalMergeSort(l, mid); NaturalMergeSort(mid + 1, r); mergeArray(l, mid, r); } } // 合并两个数组 void mergeArray(int l, int m, int r) { 
    // 初始化开始排序的下标 int left = l, mid = m + 1; int temp[SIZE]; // 初始化一个临时存放数据的数组 int start = 0; // 当左右数组都还没遍历完 while(left <= m && mid <= r) { 
    if(a[left] <= a[mid]) { 
    temp[start++] = a[left++]; } else { 
    temp[start++] = a[mid++]; } } // 将 [l, m] 或 [m + 1, r] 的数组剩余项加入到 temp 的临时数组 while(left <= m) temp[start++] = a[left++]; while(mid <= r) temp[start++] = a[mid++]; for(int i = 0; i < start; i++) { 
    a[l++] = temp[i]; // 将排序好的这部分数组数据赋值回原数组 } } 

3. 快速排序

原理：

1. 先通过找一个区间基准数的位置，从而将区间分成左右两部分，左边都小于基准数，右边都大于基准数，返回基准数下标位置
2. 然后根据下标使用分治的算法，再将左右两部分继续进行递归

第一步大致过程如下

算法流程：

1. 确定递归边界，当区间长度只有1，结束递归，即 p >= q 时
2. 每次递归时，先找一个区间基准数的位置，从而将区间分成左右两部分，左边都小于基准数，右边都大于基准数，返回基准数下标位置
3. 然后根据下标使用分治的算法，再将左右两部分继续进行递归

虽然这题要求将区间中位数设为基准数，但在实现过程中遇到了很多障碍，对于存在多个中位数数值的情况时如何处理不太会，所以还是采用的随便取基准数的快排方式（区间首位）

更多注释可查看下方的完整代码中，有助于理解

代码如下

讯享网//以a[x]为基准元素划分a[p…q]，返回左右分区调整后的基准下标. 书上2.8节有，稍稍修改。 int Partition(int x, int p, int q) //参数和返回值可根据自己需要修改。 { 
    int l = p, r = q, temp; int res = a[p]; // 取区间第一个元素为基数，即哨兵位 while(l < r) { 
    // 从右往右左，直到找到第一个小于基准元素的值，准备置换 while(a[r] >= res && l < r) r--; a[l] = a[r]; // 从左往右找，直到找到第一个大于基准元素的值，准备置换 while(a[l] <= res && l < r) l++; a[r] = a[l]; a[l] = res; // 换回来 } return l; } int RandomizedSelect(int p, int q, int k) //用任意选轴值的快速选择算法，返回a[p...q]的第k小元素的下标。 { 
    return (p + q) / 2; } int median(int p, int q) //挑出a[p…q]的中位数,并返回中位数下标，参数和返回值可根据自己需要修改。 { 
    return RandomizedSelect(p, q, p+q/2); } void QuickSort(int p,int q) //参数可根据自己需要修改。 { 
    if(p>=q)return; int x = median(p, q); int i = Partition(x,p,q); QuickSort(p,i-1); //递归 QuickSort(i+1,q); } 

完整代码

#include <iostream> #include "stdlib.h" using namespace std; const int SIZE = 10001; int a[SIZE]; int n; // 3 5 2 1 7 8 1 5 9 // 8 5 2 1 7 3 1 5 9 // 5 9 2 1 7 8 1 3 5 void RecurInsertionSort(int p, int q) //对a[p…q]的递归插入排序，参数可根据自己需要修改。 { 
    if(q == 0) return; RecurInsertionSort(p, q - 1); //对前面K-1个数进行排序 int temp = a[q]; // 要插入到前面的元素，即数组最尾部元素 int r = q - 1; // 定义r指针从后往前寻找 temp 的插入位置 while(r >= 0 && temp < a[r]) { 
    // 元素纷纷往后移一位 a[r + 1] = a[r]; r--; } a[r + 1] = temp; // 找到位置后，插入即可 } // 合并两个数组 void mergeArray(int l, int m, int r) { 
    // 初始化开始排序的下标 int left = l, mid = m + 1; int temp[SIZE]; // 初始化一个临时存放数据的数组 int start = 0; // 当左右数组都还没遍历完 while(left <= m && mid <= r) { 
    if(a[left] <= a[mid]) { 
    temp[start++] = a[left++]; } else { 
    temp[start++] = a[mid++]; } } // 将 [l, m] 或 [m + 1, r] 的数组剩余项加入到 temp 的临时数组 while(left <= m) temp[start++] = a[left++]; while(mid <= r) temp[start++] = a[mid++]; for(int i = 0; i < start; i++) { 
    a[l++] = temp[i]; // 将排序好的这部分数组数据赋值回原数组 } } void NaturalMergeSort(int l, int r) //对n个元素的自然合并排序，参数可根据自己需要修改。 { 
    int mid = (l + r) / 2; if(l < r) { 
    NaturalMergeSort(l, mid); NaturalMergeSort(mid + 1, r); mergeArray(l, mid, r); } } //以a[x]为基准元素划分a[p…q]，返回左右分区调整后的基准下标. 书上2.8节有，稍稍修改。 int Partition(int x, int p, int q) //参数和返回值可根据自己需要修改。 { 
    int l = p, r = q, temp; int res = a[p]; // 取区间第一个元素为基数，即哨兵位 while(l < r) { 
    // 从右往右左，直到找到第一个小于基准元素的值，准备置换 while(a[r] >= res && l < r) r--; a[l] = a[r]; // 从左往右找，直到找到第一个大于基准元素的值，准备置换 while(a[l] <= res && l < r) l++; a[r] = a[l]; a[l] = res; // 换回来 } return l; } int RandomizedSelect(int p, int q, int k) //用任意选轴值的快速选择算法，返回a[p...q]的第k小元素的下标。 { 
    return (p + q) / 2; } int median(int p, int q) //挑出a[p…q]的中位数,并返回中位数下标，参数和返回值可根据自己需要修改。 { 
    return RandomizedSelect(p, q, p+q/2); } void QuickSort(int p,int q) //参数可根据自己需要修改。 { 
    if(p>=q)return; int x = median(p, q); int i = Partition(x,p,q); QuickSort(p,i-1); //递归 QuickSort(i+1,q); } int main() { 
    int i; cin >> n; //递归插入排序 for(i=0;i<n;i++) { 
    cin >> a[i]; } RecurInsertionSort(0,n-1); cout << "Insert sort: "; for(i=0;i<n;i++) { 
    cout << a[i] << ' '; } //自然合并排序 for(i=0;i<n;i++) { 
    cin >> a[i]; } NaturalMergeSort(0, n - 1); cout << "\nNatural merge sort: "; for(i=0;i<n;i++) { 
    cout << a[i] << ' '; } //快速排序 for(i=0;i<n;i++) { 
    cin >> a[i]; } QuickSort(0, n-1); cout << "\nQuick sort: "; for(i=0;i<n;i++) { 
    cout << a[i] << ' '; } return 0; } 

最后

对我感兴趣的小伙伴可查看以下链接

• 我的掘金主页：https://juejin.cn/user/01358
• 博客主页：http://blog.zhangjiancong.top/
• 公众号：Smooth前端成长记录