您现在的位置是：首页 >技术交流 >【数据结构】第十五周-排序网站首页技术交流

1. 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);
}

1. 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);
 } 

1. 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-4
		a[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;
 } 

维护堆函数

1. 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);
   	}
    } 

   4. 排序综合

【题目描述】随机生成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;
 }