常用排序算法

桶排序

#include <stdio.h>
//桶排序 
int main() {
   
	int book[1001],i,j,t,n;
	for(i=0; i<=1000; i++)
		book[i]=0;
	scanf("%d",&n);//输入一个数n，表示接下来有n个数
	for(i=1; i<=n; i++) {
    //循环读入n个数，并进行桶排序
		scanf("%d",&t); //把每一个数读到变量t中
		book[t]++; //进行计数，对编号为t的桶放一个小旗子
	}
	for(i=1000; i>=0; i--) //依次判断编号1000~0的桶
		for(j=1; j<=book[i]; j++) //出现了几次就将桶的编号打印几次
			printf("%d ",i);
	getchar();
	getchar();
	return 0;
}

时间复杂度:O(N+M) M:桶的个数 N:数的个数.

冒泡排序

#include <stdio.h>
//冒泡排序 
int main() {
   
	int a[100],i,j,t,n;
	scanf("%d",&n); //输入一个数n，表示接下来有n个数
	for(i=1; i<=n; i++) //循环读入n个数到数组a中
		scanf("%d",&a[i]);
//冒泡排序的核心部分
	for(i=0; i<n-1; i++) {
    //n个数排序，只用进行n-1趟
		for(j=0; j<n-i-1; j++) //从第1位开始比较直到最后一个尚未归位的数，想一想为什么到n-i就可以了
	   {
   
			if(a[j]<a[j+1]) {
    //比较大小并交换
				t=a[j];
				a[j]=a[j+1];
				a[j+1]=t;
			}
		}
	}
	for(i=1; i<=n; i++) //输出结果
		printf("%d ",a[i]);
	return 0;
}

时间复杂度:O(N^2)

快速排序

#include<iostream>
using namespace std;
int arr[101],n;

void quicksort(int left,int right)
{
   
	int i,j,t,temp;
	if(left > right)
		return;
	temp=arr[left];
	i = left;
	j = right;
	while(i!=j)
	{
   
		//先从右往左找 
		while(arr[j]>=temp&&i<j)
		{
   
			j--;
		}
		//再从左往右找
		while(arr[i]<=temp && i < j) 
		{
   
			i++;
		}
		//交换两个数在数组中的位置
		if(i<j) //当哨兵i和j没有相遇时
		{
   
			t = arr[i];
			arr[i]=arr[j];
			arr[j] = t;
		 } 
	}
	//将基数归位
	arr[left] = arr[i];
	arr[i] = temp;
	quicksort(left,i-1);//继续处理左边的 
	quicksort(i+1,right); //继续处理右边的 
}

int main()
{
   
	cin>>n;
	for(int i = 1; i<=n; i++)
	{
   
		cin>>arr[i];
	}
	quicksort(1,n);
	for(int i = 1; i<=n; i++)
	{
   
		cout<<arr[i]<<" ";
	}
	return 0;
 } 

时间复杂度:O (NlogN)