欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

排序

程序员文章站 2022-04-25 15:18:45
...

目录

冒泡排序

选择排序

插入排序

快速排序


冒泡排序(时间复杂度排序, 空间复杂度排序,稳定)

#include<stdio.h>
void bubbleSort(int a[], int n)
{
	for (int i = 0; i < n - 1;i++)       //n-1轮
	for (int j = 0; j < n - 1 - i; j++)
	if (a[j]>a[j + 1])                //从小到大排序
	{
		int temp = a[j];           //交换相邻的元素
		a[j] = a[j + 1];
		a[j + 1] = temp;
	}
}
int main()
{
	int a[10] = { 6, 3, 4, 9, 1, 2, 0, 3, 8, 5 };
	bubbleSort(a, 10);
	for (int i = 0; i < 10; i++)
	{
		printf("%d ", a[i]);
	}
	return 0;
}
0 1 2 3 3 4 5 6 8 9 请按任意键继续. . .

选择排序(时间复杂度排序, 空间复杂度排序,不稳定)

#include<stdio.h>
void selectSort(int a[], int n)
{
	for (int i = 0; i < n - 1; i++)   //n-1轮
	{ 
		int pos = i;                 //初始位置为当前位置
		for (int j = i+1; j < n; j++)     //遍历i后面的元素,寻找最小的元素
		if (a[pos]>a[j])           //从小到大排序    
		{
			pos = j;              //记录比a[pos]小的位置
		}
		int temp = a[pos];         //将最小的元素和当前位置的元素交换
		a[pos] = a[i];
		a[i] = temp;
	}
}
int main()
{
	int a[10] = { 6, 3, 4, 9, 1, 2, 0, 3, 8, 5 };
	selectSort(a, 10);
	for (int i = 0; i < 10; i++)
	{
		printf("%d ", a[i]);
	}
	return 0;
}
0 1 2 3 3 4 5 6 8 9 请按任意键继续. . .

插入排序(时间复杂度排序, 空间复杂度排序,稳定)

#include<iostream>
using namespace std;
void insertSort(int a[],int n)
{
	for (int i = 1; i < n; i++)
	{
		int temp = a[i];
		int j = i - 1;
		while (j >= 0 && temp<a[j])
		{
			a[j + 1] = a[j];
			j--;
		}
		a[j + 1] = temp;
	}
}
int main()
{
	int a[10] = { 6, 3, 4, 9, 1, 2, 0, 3, 8, 5 };
	insertSort(a, 10);
	for (int i = 0; i < 10; i++)
		printf("%d ", a[i]);
	return 0;
}
0 1 2 3 3 4 5 6 8 9 请按任意键继续. . .

快速排序(时间复杂度排序, 空间复杂度排序,不稳定)

排序

#include<stdio.h>
int takePart(int a[], int left, int right)  //一份为二
{
	int mid = left;
	int i = left, j = right;
	while (i < j)
	{
		while (i<j&&a[mid]<a[j]) --j;
		while (i < j&&a[i] <= a[mid]) ++i;
		if (i < j)
		{
			int temp = a[i];
			a[i] = a[j];
			a[j] = temp;
		}
	}
	int temp = a[mid];
	a[mid] = a[j];
	a[j] = temp;
	return i;
}
void quickSort(int a[], int left,int right)// 从小到大
{
	if (left >= right)  return;  //递归出口
	int k=takePart(a,left,right);  //返回中间数的位置
	quickSort(a, left, k - 1);   //左边排序
	quickSort(a, k + 1, right);   //右边排序
}
int main()
{
	int a[10] = { 6, 3, 4, 9, 1, 2, 0, 3, 8, 5 };
	quickSort(a, 0,9);
	for (int i = 0; i < 10; i++)
	{
		printf("%d ", a[i]);
	}
	return 0;
}
0 1 2 3 3 4 5 6 8 9 请按任意键继续. . .

希尔排序(时间复杂度约为排序)

希尔排序是插入排序的进阶版, 普通插入排序的g=1, 而希尔排序g=1,4,7,10...

#include<iostream>
#include<vector>
#include<cstdio>
using namespace std;
vector<int>G;

void insertSort(int a[],int n,int g)   //插入排序, 以g为步长, 把1改为g就可以了, 其他的和插入排序一样
{
	for (int i = 1; i < n; i++)
	{
		int temp = a[i];
		int j = i - g;
		while (j >= 0 && temp<a[j])
		{
			a[j + g] = a[j];
			j-=g;

		}
		a[j + g] = temp;
	}
}
void shellSort(int a[], int n)
{
	//得到G[]
	for (int h = 1; h <= n;)
	{
		G.push_back(h);   //产生g=1.4.7.10...
		h = 3 * h + 1;
	}

	for (int i = G.size() - 1; i >= 0; i--)
		insertSort(a, n, G[i]);
}
int main()
{
	int m=8;
	int a[8] = {6,3,1,9,7,0,4,5};
	
	shellSort(a, m);

	for (int i = 0; i <m; i++)
		printf("%d ", a[i]);
	return 0;
}

 

0 1 3 4 5 6 7 9 请按任意键继续. . .

 

相关标签: 排序