- 1. 快速排序
【问题描述】输入一组数据，以0作为输入的结束，分别采用冒泡排序、选择排序、快速排序的方法，对其进行从小到大的排序，给出排序后的结果。
【输入形式】一组数据，以0作为输入的结束
【输出形式】三种排序后的结果
【样例输入】
9 8 4 5 7 2 10 6 0
【样例输出】
2 4 5 6 7 8 9 10
2 4 5 6 7 8 9 10
2 4 5 6 7 8 9 10
//快速排序
#include<iostream>
using namespace std;int partition(int arr[], int low, int high) {int num = arr[low];while(low < high) {while(low < high && arr[high] > num) {high--;}arr[low] = arr[high];while(low < high && arr[low] <=num) {low++;}arr[high] = arr[low];}arr[low] = num;return low;
}void QuickSort(int arr[],int L,int R)
{if(L<R){int mid=partition(arr,L,R);QuickSort(arr,L,mid-1);QuickSort(arr,mid+1,R);}
}
void BubbleSort(int arr[],int n)
{for(int i=0;i<n-1;i++){for(int j=i+1;j<n;j++){if(arr[i]>arr[j]){int temp=arr[i];arr[i]=arr[j];arr[j]=temp;}}}
}
void ChooseSort(int arr[],int n)
{int minnum;for(int i=0;i<n-1;i++){minnum=i;for(int j=i+1;j<n;j++){if(arr[minnum]>arr[j])minnum=j;} int temp=arr[i];arr[i]=arr[minnum];arr[minnum]=temp;}}
void travel(int arr[],int n)
{for(int i=0;i<n;i++)cout<<arr[i]<<" ";cout<<endl;}
int main()
{int x;int a[100],b[100],c[100];int n=0;cin>>x;while(x!=0){a[n]=x;b[n]=x;c[n]=x;cin>>x;n++;}
// travel(a,n);BubbleSort(a,n);ChooseSort(b,n);QuickSort(c,0,n-1);travel(a,n);travel(b,n);travel(c,n);
}- 2. 希尔排序
【问题描述】给出一组数据，请用希尔排序将其按照从小到大的顺序排列好。
【输入形式】原始数据，以0作为输入的结束；第二行是增量的值，都只有3个。
【输出形式】每一趟增量排序后的结果
【样例输入】
8 3 6 1 68 12 19 3 1 0
5 3 1
【样例输出】
8 3 3 1 68 12 19 6 1
1 3 1 8 6 3 19 68 12
1 1 3 3 6 8 12 19 68
【样例输入】
5 3 9 8 2 4 1 7 10 6 0
4 2 1
【样例输出】
2 3 1 7 5 4 9 8 10 6
1 3 2 4 5 6 9 7 10 8
1 2 3 4 5 6 7 8 9 10
//希尔排序
//8 3 6 1 68 12 19 3 1 0
#include<iostream>
using namespace std;void Shell(int a[],int n,int incr)
{int j;
for(int i=0;i+incr<n;i++)
{int x=a[i+incr];for( j=i;j>=0;j-=incr){if(x<a[j]) //18<10{a[j+incr]=a[j];}else break;}a[j+incr]=x;
}
}
void ShellSort(int a[],int n,int d[])
{for(int i=0;i<3;i++){Shell(a,n,d[i]);for(int j=0;j<n;j++)cout<<a[j]<<" ";cout<<endl;}
}
int main()
{int a[100],n,i=0;while(cin>>a[i]&&a[i])//输入数据 i++; n=i;
// Shell(a,n);
// for(int i=0;i<n;i++)
// cout<<a[i]<<" ";int d[10];cin>>d[0]>>d[1]>>d[2];ShellSort(a,n,d);}
- 3. 堆排序
【问题描述】请用堆排序的方法对一组数据进行排序，并给出建堆以及每一趟堆排序的结果。
【输入形式】一组数据，以0作为输入的结束。
【输出形式】建大根堆的结果，以及每一趟堆排序的结果。
【样例输入】
8 3 6 1 68 12 0
【样例输出】
68 8 12 1 3 6
12 8 6 1 3 68
8 3 6 1 12 68
6 3 1 8 12 68
3 1 6 8 12 68
1 3 6 8 12 68
【样例输入】
12 9 26 11 38 52 99 27 66 15 32 0
【样例输出】
99 66 52 27 38 12 26 9 11 15 32
66 38 52 27 32 12 26 9 11 15 99
52 38 26 27 32 12 15 9 11 66 99
38 32 26 27 11 12 15 9 52 66 99
32 27 26 9 11 12 15 38 52 66 99
27 15 26 9 11 12 32 38 52 66 99
26 15 12 9 11 27 32 38 52 66 99
15 11 12 9 26 27 32 38 52 66 99
12 11 9 15 26 27 32 38 52 66 99
11 9 12 15 26 27 32 38 52 66 99
9 11 12 15 26 27 32 38 52 66 99
排序算法：堆排序【图解+代码】_哔哩哔哩_bilibili
//堆排序
#include<iostream>
#include<bits/stdc++.h>
using namespace std;void SiftAdjust(int a[],int n,int i)
{//n是a数组有效数据的范围，它是慢慢变小的//i是要调整的那个节点的编号 int f,left;//f 用来记忆双亲 left算出i的左孩子编号 for(f=i,left=2*i+1;left<=n-1;)//计算新的孩子{//f记下要调整的i号节点，keft就变成右孩子的下标 if(left+1<=n-1 && a[left]<a[left+1] )//右孩子存在，且，右边值更大 left=left+1;//left++ left就变成右孩子的下标 if(a[left]>a[f])//孩子的最大值和双亲f比，若孩子更大，则交换 {int t=a[left];a[left]=a[f];a[f]=t;}else break; //孩子的值 小，就结束 return f=left; //继续向下调整，刚才的孩子成为新的双亲，再上去计算新的孩子 left=2*f+1; //计算出新孩子，这句话放for表达式3也可以 }}
void HeapSort(int a[],int n)
{//8 3 6 1 68 12 19 3 1//k=0 1 2 3 4 5 6 7 8//调整 中间节点 for(int i=(n-2)/2;i>=0;i--){SiftAdjust(a,n,i);} //调整根节点 for(int j=0;j<n;j++)cout<<a[j]<<" "; cout<<endl;for(int i=0;i<n-1;i++){int t=a[n-1-i];// n-1 n-2 n-3 n-4a[n-1-i]=a[0];a[0]=t;//交换第一个与最后一个数SiftAdjust(a,n-1-i,0);//调整剩下n-1-i个 维护根 for(int j=0;j<n;j++)cout<<a[j]<<" ";cout<<endl;}
}
int main()
{int a[100],i=0;while(cin>>a[i]&&a[i]){i++;}int n=i;HeapSort(a,n);return 0;} 维护堆函数
-
4. 排序综合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);}}
【题目描述】随机生成10000、20000、40000、80000、160000个整形数据，监测冒泡排序、选择排序、快速排序这三种排序方法各自所需要的时间，并显示其排序时间。可以将前面做过的其他排序方法加入，进行对比。
【说明】此题仅提交、不测评、不计分。
//希尔排序
//8 3 6 1 68 12 19 3 1 0
#include<iostream>
#include<ctime>
#include<bits/stdc++.h>
using namespace std;void InsSort(int a[],int n)
{int j;for(int i=0;i<n-1;i++){int x=a[i+1];for(j=i;j>=0;j--){if(x<a[j]){a[j+1]=a[j];}else break;}a[j+1]=x;}
}void Shell(int a[],int n,int incr)
{int j;
for(int i=0;i+incr<n;i++)
{int x=a[i+incr];for( j=i;j>=0;j-=incr){if(x<a[j]) //18<10{a[j+incr]=a[j];}else break;}a[j+incr]=x;
}
}
void ShellSort(int a[],int n,int d[])
{for(int i=0;i<7;i++){Shell(a,n,d[i]);
// for(int j=0;j<n;j++)
// cout<<a[j]<<" ";}
}
int main()
{int a[200000],n=200000,i=0;int b[200000];srand(time(NULL));for(i=0;i<n;i++)b[i]=a[i]=rand();clock_t start,end;start=clock();int d[10]={79,11,7,5,3,1};//越多越快 ShellSort(a,n,d);end=clock();cout<<(double)(end-start)/CLOCKS_PER_SEC;start=clock();InsSort(b,n);end=clock();cout<<(double)(end-start)/CLOCKS_PER_SEC;}
