Home Article 经典排序算法汇总

经典排序算法汇总

Release time:2020-08-23 19:42:03 Author:一蓑烟雨 Reading volume:347

各种排序算法复杂度:

1.冒泡排序


#include <stdio.h>
#include <time.h>
#include <stdlib.h>

void get_array(int a[], int length)
{
	int i;
	//int size = sizeof(a) / sizeof(a[0]);   //在调用的函数里面不能求数组长度
	//printf("shuru 5 ge shu
");
	srand(time(NULL));
	for(i = 0; i < length; i++)
	{
		a[i] = rand() % 1000;
	}
}

void sort(int a[], int length)
{
	int i, j;
	for(i = 0; i < length - 1; i++)
	{
		for (j = 0; j < length - i - 1; j++)
		{
			if (a[j] > a[j + 1])
			{
			#if 0
				int tmp = a[j];
				a[j] = a[j + 1];
				a[j + 1] = tmp;
			#endif
				a[j] = a[j] + a[j + 1];
				a[j + 1] = a[j] - a[j + 1];
				a[j] = a[j] - a[j + 1];
			}
		}
	}
	
}

void print_array(int a[], int length)
{
	int i;
	for (i = 0; i < length; i++)
	{
		printf("%d ", a[i]);
	}
	printf("
");
	
}

int main()
{
	int i, j, a[10] = {0};

	get_array(a, sizeof(a) / sizeof(a[0]));

	sort(a, sizeof(a) / sizeof(a[0]));

	print_array(a, sizeof(a) / sizeof(a[0]));


	return 0;
}
2.选择排序
#include <stdio.h>

void SelectSort(int *a, int length)
{
	int i, j, min, index;

	for (i = 0; i < length - 1; i++)
	{
		min = a[i];	
		index = i;
		for (j = i + 1; j <= length - 1; j++)
		{
			if (a[j] < min)
			{
				min = a[j];
				index = j;
			}
		}
		if (index != i)
		{
			a[i] = a[i] + a[index];
			a[index] = a[i] - a[index];
			a[i] = a[i] - a[index];
		}
	}
}

int main()
{
	int i;
	//int array[] = {4, 2, 7, 9, 0, 6, 2, 1, 8, 3};
	int array[10000] = {0};
	srand(time(NULL));
	for (i = 0; i < 10000; i++)
	{
		array[i] = rand() % 1000 + 1;
	}

	SelectSort(array, sizeof(array) / sizeof(array[0]));

	for (i = 0; i < sizeof(array) / sizeof(array[0]); i++)
	{
		printf("%d ", array[i]);
	}
	printf("
");

	return 0;
}

3.插入排序


#include <stdio.h>

void InsertSort(int *a, int length)
{
	int i, j, tmp;

	for (i = 1; i < length; i++)
	{
		tmp = a[i];	
		for (j = i - 1; j >= 0; j--)
		{
			if (tmp < a[j])
			{
				a[j + 1] = a[j];
			}
			else
			{
				break;
			}
		}
		a[j + 1] = tmp;
	}
}

int main()
{
	int i;
	//int array[] = {4, 2, 7, 9, 0, 6, 2, 1, 8, 3};
	int array[10000] = {0};
	srand(time(NULL));
	for (i = 0; i < 10000; i++)
	{
		array[i] = rand() % 1000 + 1;
	}

	InsertSort(array, sizeof(array) / sizeof(array[0]));

	for (i = 0; i < sizeof(array) / sizeof(array[0]); i++)
	{
		printf("%d ", array[i]);
	}
	printf("
");

	return 0;
}

4.希尔排序


#include <stdio.h>

void InsertSort(int *a, int length)
{
	int i, j, tmp, h;

	for (h = length / 2; h > 0; h /= 2)
	{
		for (i = h; i < length; i++)   
		{
			tmp = a[i];	
			for (j = i - h; j >= 0; j = j - h)   //j = 3 j > 0 j--    j = 2 j >= 0 j--
			{
				if (tmp < a[j])
				{
					a[j + h] = a[j];
				}	
				else
				{
					break;
				}
			}
			a[j + h] = tmp;
		}
	}
}

int main()
{
	int i;
	//int array[] = {4, 2, 7, 9, 0, 6, 2, 1, 8, 3};
	int array[10000] = {0};
	srand(time(NULL));
	for (i = 0; i < 10000; i++)
	{
		array[i] = rand() % 1000 + 1;
	}

	InsertSort(array, sizeof(array) / sizeof(array[0]));

	for (i = 0; i < sizeof(array) / sizeof(array[0]); i++)
	{
		printf("%d ", array[i]);
	}
	printf("
");

	return 0;
}

5.归并排序


#include <stdio.h>
#include <stdlib.h>

void Merge(int *a, int start, int mid, int end)
{
	int LeftLen = mid - start + 1;
	int RightLen = end - mid;
	int *L = (int *)malloc(sizeof(int) * LeftLen);
	int *R = (int *)malloc(sizeof(int) * RightLen);

	int i, k, j;
	for (i = 0, k = start; i < LeftLen; i++, k++)
	{
		L[i] = a[k];
	}
	for (j = 0; j < RightLen; j++, k++)
	{
		R[j] = a[k];
	}

	for (i = 0, j = 0, k = start; i < LeftLen && j < RightLen; k++)
	{
		if (L[i] < R[j])
		{
			a[k] = L[i++];
		}
		else
		{
			a[k] = R[j++];
		}
	}

	if (j < RightLen)
	{
		for (; j < RightLen; j++, k++)
		{
			a[k] = R[j];
		}
	}
	if (i < LeftLen)
	{
		for (; i < LeftLen; i++, k++)
		{
			a[k] = L[i];
		}
	}
}

void MergeSort(int *a, int start, int end)
{
	if (start >= end)
	{
		return;
	}

	int mid = (start + end) / 2;
	MergeSort(a, start, mid);            //拆分,拆成数组只有1个元素
	MergeSort(a, mid + 1, end);

	Merge(a, start, mid, end);
}

int main()
{
	int i;
	//int array[] = {4, 2, 7, 9, 0, 6, 2, 1, 8, 3};
	int array[10000] = {0};
	srand(time(NULL));
	for (i = 0; i < 10000; i++)
	{
		array[i] = rand() % 1000 + 1;
	}

	MergeSort(array, 0, sizeof(array) / sizeof(array[0]) - 1);

	for (i = 0; i < sizeof(array) / sizeof(array[0]); i++)
	{
		printf("%d ", array[i]);
	}
	printf("
");

	return 0;
}
6.快速排序
#include <stdio.h>

void QuickSort(int *a, int start, int end)
{
	int x = start;
	int y = end;
	int base = a[x];

	if (x >= y)
	{
		return;
	}

	while (x < y)
	{
		while (a[y] > base && x < y)
		{
			y--;
		}
		if (x < y)
		{
			a[x++] = a[y];
		}
		while (a[x] < base && x < y)
		{
			x++;
		}
		if (x < y)
		{
			a[y--] = a[x];
		}
	}
	a[x] = base;

	QuickSort(a, start, x - 1);
	QuickSort(a, x + 1, end);
}

int main()
{
	int i;
	//int array[] = {4, 2, 7, 9, 0, 6, 2, 1, 8, 3};
	int array[100000] = {0};
	srand(time(NULL));
	for (i = 0; i < 100000; i++)
	{
		array[i] = rand() % 1000 + 1;
	}

	QuickSort(array, 0, sizeof(array) / sizeof(array[0]) - 1);

	for (i = 0; i < sizeof(array) / sizeof(array[0]); i++)
	{
		printf("%d ", array[i]);
	}
	printf("
");

	return 0;
}
7.堆排序
#include <stdio.h>

/*
函数描述:构建大顶堆
函数参数:数组  根节点的下标  最后一个结点的下标
*/
void AdjustMaxHeap(int *a, int root, int last)
{
	int i, child;
	int tmp = a[root];
	for (; 2 * root + 1 <= last; root = child)
	{
		child = 2 * root + 1;
		if (child + 1 <= last && a[child] < a[child + 1])
		{
			child++;
		}
		if (a[child] > a[root])
		{
			a[root] = a[child];
			a[child] = tmp;
		}
		else
		{
			break;
		}
	}
}

void swap(int *x, int *y)
{
	int t = *x;
	*x = *y;
	*y = t;
}

void HeapSort(int *a, int length)
{
	//构建大顶堆
	int i;
	for (i = length / 2 - 1; i >= 0; i--)
	{
		AdjustMaxHeap(a, i, length - 1);		
	}

	//调整大顶堆
	for (i = length - 1; i > 0; i--)
	{
		swap(&a[0], &a[i]);
		AdjustMaxHeap(a, 0, i - 1);
	}
}

int main()
{
	int i;
	//int array[] = {4, 2, 7, 9, 0, 6, 2, 1, 8, 3};
	int array[100000] = {0};
	srand(time(NULL));
	for (i = 0; i < 100000; i++)
	{
		array[i] = rand() % 1000 + 1;
	}

	HeapSort(array, sizeof(array) / sizeof(array[0]));

	for (i = 0; i < sizeof(array) / sizeof(array[0]); i++)
	{
		printf("%d ", array[i]);
	}
	printf("
");

	return 0;
}
8.计数排序
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
//计数排序
void CountSort(int *a, int len)
{
	assert(a);
	//通过max和min计算出临时数组所需要开辟的空间大小
	int max = a[0], min = a[0];
	for (int i = 0; i < len; i++){
		if (a[i] > max)
			max = a[i];
		if (a[i] < min)
			min = a[i];
	}
	//使用calloc将数组都初始化为0
	int range = max - min + 1;
	int *b = (int *)calloc(range, sizeof(int));
	//使用临时数组记录原始数组中每个数的个数
	for (int i = 0; i < len; i++){
		//注意:这里在存储上要在原始数组数值上减去min才不会出现越界问题
		b[a[i] - min] += 1;
	}
	int j = 0;
	//根据统计结果,重新对元素进行回收
	for (int i = 0; i < range; i++){
		while (b[i]--){
			//注意:要将i的值加上min才能还原到原始数据
			a[j++] = i + min;
		}
	}
	//释放临时数组
	free(b);
	b = NULL;
}
//打印数组
void PrintArray(int *a, int len)
{
	for (int i = 0; i < len; i++){
		printf("%d ", a[i]);
	}
	printf("
");
}
int main()
{
	int a[] = { 3, 4, 3, 2, 1, 2, 6, 5, 4, 7 };
	printf("排序前:");
	PrintArray(a, sizeof(a) / sizeof(int));
	CountSort(a, sizeof(a) / sizeof(int));
	printf("排序后:");
	PrintArray(a, sizeof(a) / sizeof(int));
	system("pause");
	return 0;
}

9.桶排序



#include <stdio.h>
void main()
{
    int a[11],i,j,t;
    for(i=0;i<=10;i++)
	{
		a[i]=0;//初始化为0
	}
	for(i=0;i<5;i++)//循环读入5个数
	{
		scanf("%d",&t);//把每一个数读到变量t中
		a[t]++;//进行计数
	}
	for(i=0;i<=10;i++)//依次判断a[0]~a[10]
	{
		for(j=0;j<a[i];j++)//出现了几次就打印几次
		{
			printf("%d",i);
		}
	}
}
 

10.基数排序


#include <stdio.h>
#include <stdlib.h>

void RadixSort(int *a, int length)
{
	int max = a[0], i, radix = 1;
	for (i = 1; i < length; i++)
	{
		if (a[i] > max)
		{
			max = a[i];
		}
	}

	int *t = (int *)malloc(sizeof(int) * length);
	while (max / radix != 0)
	{
		int bucket[10] = {0};                 //记录每个桶有多少个数字
		for (i = 0; i < length; i++)
		{
			bucket[a[i] / radix % 10]++;
		}
		
		for (i = 1; i <= 9; i++)
		{
			bucket[i] = bucket[i] + bucket[i - 1];
		}

		for (i = length - 1; i >= 0; i--)
		{
			t[bucket[a[i] / radix % 10] - 1] = a[i];
			bucket[a[i] / radix % 10]--;
		}

		for (i = 0; i < length; i++)
		{
			a[i] = t[i];
		}

		radix = radix * 10;
	}

	free(t);
}

int main()
{
	int i;
	//int array[] = {400, 2234, 789, 119, 11110, 666, 22, 11, 78, 3};
	int array[10000] = {0};
	srand(time(NULL));
	for (i = 0; i < 10000; i++)
	{
		array[i] = rand() % 1000 + 1;
	}

	RadixSort(array, sizeof(array) / sizeof(array[0]));

	for (i = 0; i < sizeof(array) / sizeof(array[0]); i++)
	{
		printf("%d ", array[i]);
	}
	printf("
");

	return 0;
}


  
I want to comment

Search

classification

Leave a message
http://blog.rjxj513.com/
User login
You have not written any reviews yet!
You have commented!
Can only praise once!
You have a collection!