1305: 排序算法
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：106
解决：43
题目描述
# 排序算法
## 插入类排序
### 桶排序
> 算法思想：用空间复杂度换取时间复杂度，待排序的数据分别放入不同的桶中，这些桶之间其实是有序的。然后在这些桶中将分在里面的数据进行排序。最终就完成了整个序列的排序
#### 代码展示
```cpp
#include<iostream>
using namespace std;
int BarrelSort(int R[],int n)
{
int k;
for(int i=0;i<n;i++)
{
cin>>k;//获取到序列的值
R[k]=1;//放入对应的桶
}
return 0;
}
int main()
{
int a[100]={};
int n=100;
int k=8;
BarrelSort(a,k);
for(int i=0;i<n;i++)
if(a[i]==1)
cout<<i<<" ";
return 0;
}
```
### 直接插入排序
> 算法思想：每趟将一个待排序的关键字按照其值的大小插入到已经排好的部分有序序列的适当位置上，直到所有待排关键字都被插入到有序序列中为止
#### 代码展示
```cpp
#include<iostream>
using namespace std;
int insertSort(int R[],int n)//待排关键字存储在R[]中，默认为整型，个数为n
{
int temp,i,j;
for(int i=1;i<n;i++)//将待插入关键字暂存于temp中
{
temp=R[i];
j=i-1;
/*下面这个循环完成了从待排关键字之前的关键字开始扫描，
如果大于待排关键字，则后移一位*/
while(j>=0&&temp<R[j])
{
R[j+1]=R[j];
--j;
}
R[j+1]=temp; //找到插入位置，将temp中暂存的待排关键字插入。
}
return 0;
}
int main()
{
int a[8]={49,38,65,97,76,13,27,49};
int n=8;
insertSort(a,n);
for(int i=0;i<n;i++)
cout<<a[i]<<" ";
return 0;
}
```
### 折半插入排序
>算法思想：折半插入排序的基本思想和直接插入排序类似，区别是查找插入位置的方法不同，折半插入排序是采用折半查找法来查找插入位置的。
#### 代码展示
```cpp
#include<iostream>
using namespace std;
void BinaryInsertSort(int R[], int n){
int temp;
for(int i = 1; i < n; i++){
int low = 0;
int hight = i-1;
temp = R[i];
while(hight>=low){//折半查找，找到要插入的位置。
int mid = ( low + hight ) / 2;
if (R[mid] > temp){
hight = mid - 1;
}else{
low = mid + 1;
}
}
for (int j = i-1; j > hight; j--) {//处理序列，腾出要插入的位置
R[j+1] = R[j];
}
R[hight+1] = temp;//将temp中暂存的待排关键字插入。
}
}
int main(){
int a[8]={49,38,65,97,76,13,27,49};
int n=8;
BinaryInsertSort(a,n);
for(int i=0;i<n;i++)
cout<<a[i]<<" ";
return 0;
}
```
### 希尔排序（缩小增量排序）
>算法思想：本质还是插入排序，只不过是将待排序列按某种规则分成几个子序列，分别对这几个子序列进行直接插入排序。这个规则的体现就是增量的选取，如果增量为1，就是直接插入排序。例如：先以增量5来分割序列，即将下标为0、5、10、15...的关键字分成一组，将下标为1、6、11、16...的关键字分成另一组等。然后分别对这些组进行直接插入排序，这就是一趟希尔排序。再以增量2分割，即将下标为0、2、4、6、8...的关键字分成一组，将下标为1、3、5、7、9...的关键字分成另一组等，然后分别对这些组进行直接插入排序，这就完成了一趟希尔排序。最后以增量为1分割整个序列，其实就是对整个序列进行一趟直接插入排序，从而完成整个希尔排序。
## 交换类排序
### 冒泡排序
>算法思想：他是通过一系列的"交换"动作完成的。首先第一个关键字和第二个关键字比较，如果第一个大，则二者交换，否则不交换；然后第二个关键字和第三个关键字比较，如果第二个大，则二者交换，否则不交换......一直按这种方法进行下去，最终最大的那个关键字被交换到了最后，一趟冒牌排序完成。经过多趟这样的排序，最终使整个序列有序。这个过程中，大的关键字像石头一样"沉底",小的关键字像气泡一样逐渐向上"浮动"，冒泡排序由此而来。
#### 代码展示
```cpp
#include<iostream>
using namespace std;
int bubbleSort(int R[],int n)//默认待排序关键字为整型
{
int flag;
int temp;
for(int i=n-1;i>=1;i--)
{
flag=0;//变量flag用来标记本趟排序是否发生了交换
for(int j=1;j<=i;j++)
{
if(R[j-1]>=R[j])
{
temp=R[j];
R[j]=R[j-1];
R[j-1]=temp;
flag=1;//如果没发生交换，则flag的值为0；如果发生
//交换，则flag的值为1
}
}
if(flag==0)//一趟排序过程中没有发生关键字交换，则证明序列
return 0;//有序，排序结束
}
return 0;
}
int main()
{
int a[8]={49,38,65,97,76,13,27,49};
int n=8;
bubbleSort(a,n);
for(int i=0;i<n;i++)
cout<<a[i]<<" ";
return 0;
}
```
### 快速排序
>算法思想：快速排序也是"交换"类排序，它通过多次划分操作实现排序。以升序为例，其执行流程可以概括为：每一趟选择当前所有子序列中的一个关键字（通常是第一个）作为枢轴，将子序列中比较轴小的移到枢轴前边，比枢轴大的移到枢轴后边；当本趟所有子序列都被枢轴以上述规则划分完毕后会得到新的一组更短的子序列，它们成为下一趟划分的初始序列集。
#### 代码展示
```cpp
#include<iostream>
using namespace std;
int QuickSort(int R[],int low,int high)
{//对从R[low]到R[high]的关键字进行排序
int temp;
int i=low,j=high;
if(low<high)
{
temp=R[low];
/*下面这个循环完成了一趟排序，即将数组中小于temp的关键字放在左边，
大于temp的关键字放在右边*/
while(i<j)
{
while(j>i&&R[j]>=temp)--j;//从右往左扫描，找到一个小于temp的关键字
if(i<j)
{
R[i]=R[j];//放在temp左边
++i;//i右移
}
while(i<j&&R[i]<temp)++i;
if(i<j)
{
R[j]=R[i];//放在temp右边
--j;//j左移一位
}
}
R[i]=temp;//将temp 放在最终位置
QuickSort(R,low,i-1);//递归地对temp左边的关键字进行排序
QuickSort(R,i+1,high);//递归的对temp 右边的关键字进行排序
}
return 0;
}
int main()
{
int a[8]={49,38,65,97,76,13,27,49};
int n=8;
QuickSort(a,0,n-1);
for(int i=0;i<n;i++)
cout<<a[i]<<" ";
return 0;
}
```
## 选择类排序
### 简单选择排序
>算法思想：简单选择排序采用最简单的选择方式，从头至尾顺序扫描序列，找出最小的一个关键字，和第一个关键字交换，接着从剩下的关键字中继续这种选择和交换，最终使序列有序。
#### 代码展示
```cpp
#include<iostream>
using namespace std;
int SelectSort(int R[],int n)
{
int k;
int temp;
for(int i=0;i<n;i++)
{
k=i;/*这个循环是算法的关键，它从无序序列中挑出一个最小的关键字*/
for(int j=i+1;j<n;j++)
if(R[k]>R[j])
k=j;
/*最小的关键字和无序序列第一个关键字交换*/
temp=R[i];
R[i]=R[k];
R[k]=temp;
}
return 0;
}
int main()
{
int a[8]={49,38,65,97,76,13,27,49};
int n=8;
SelectSort(a,n);
for(int i=0;i<n;i++)
cout<<a[i]<<" ";
return 0;
}
```
### 堆排序
>算法思想：堆是一种数据结构，可以把堆看成一颗完成二叉树，这颗完成二叉树满足：任何一个非叶节点的值都不大于（或不小于）其左右孩子结点的值。若父亲大孩子小，则这样的堆叫作大顶堆；若父亲小孩子大，则这样的堆叫做小顶堆。
根据堆的定义知道，代表堆的这颗完全二叉树的根结点的值最大（或最小）的，因此将一个无序序列调整为一个堆，就可以找出这个序列的最大（最小）值，然后将找出的这个值交换到序列的最后（最前），这样，有序序列关键字增加1个，无序序列中关键字减少1个，对新的无序序列重复这样的，就实现了排序。这就是堆排序的思想。
堆排序中对最关键的操作是将序列调整为堆。整个排序的过程就是通过不断调整，使得不符合堆定义的完全二叉树变为符合堆定义的完全二叉树
### 二路归并排序
>算法思想：归并排序可以看作一个分而治之的过程：先将整个序列分为两半，对每一半分别进行归并排序，将得到的两个有序序列，然后将这两个序列归并成一个序列即可。
#### 代码展示
```cpp
#include<iostream>
using namespace std;
int mege(int A[],int low,int mid,int high)
{
int B[100]={};
for(int i=low;i<=high;i++)
B[i]=A[i];
int k1=low,k2=mid+1;
for(int i=low;i<=high;i++)
{
if(k1>mid)A[i]=B[k2++];//前半段已经排完
else if(k2>high)A[i]=B[k1++];//后半段已经排完
else if(B[k1]<B[k2])A[i]=B[k1++];//谁小排谁
else A[i]=B[k2++];
}
return 0;
}
int mergeSort(int A[],int low,int high)
{
if(low<high)
{
int mid=(low+high)/2;
mergeSort(A,low,mid);//归并排序前半段
mergeSort(A,mid+1,high);//归并排序后半段
mege(A,low,mid,high);/*将A数组中的low到mid和
mid+1到high范围内的两段有序序列归并成一段有序序列 */
}
return 0;
}
int main()
{
int a[8]={49,38,65,97,76,13,27,49};
int n=8;
mergeSort(a,0,n-1);
for(int i=0;i<n;i++)
cout<<a[i]<<" ";
return 0;
}
```
输入
第一行输入n
第二行输入n个数
第二行输入n个数
输出
从小到大输出n个数
样例输入 复制
10
10 9 1 2 3 6 5 4 7 8样例输出 复制
1 2 3 4 5 6 7 8 9 10