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

十大经典排序算法

程序员文章站 2022-04-10 21:02:15
...

十大经典排序算法(附有动图演示哦十大经典排序算法)

       十大经典排序算法

十大经典排序算法

A>交换排序---冒泡排序

  a>冒泡排序（Bubble Sort）

 算法描述:比较两个相邻的元素,如果升序的话,前面的比后面的大,就交换,这样一轮下来,就会找到这组数据中最大的元素,然后抛开这个元素继续重复上述步骤.知道排完为止.   

   b>冒泡排序（Bubble Sort）动图演示

十大经典排序算法

b>冒泡排序（Bubble Sort）代码实现

#include<stdio.h>
#include<stdlib.h>
void swap(int *a, int *b){
	int ret = 0;
	ret = *a;
	*a = *b;
	*b = ret;
}
void Bubble_sort(int *arr,int size){
	int i = 0;
	int j = 0;
	for ( i = 0; i < size-1; i++)
	{
		for (j = 0; j < size-1-i; j++)
		{
			if (arr[j]>arr[j+1])//这是升序的写法,降序将改为if(arr[j]<arr[j+1])
			{
				swap(&arr[j], &arr[j+1]);
			}
		}
	}
}
int main(){
	int i = 0;
	int arr[10] = { 2, 0, 4, 9, 3, 6, 8, 7, 1, 5 };
	int size = sizeof(arr) / sizeof(arr[0]);
	Bubble_sort(arr,size);
	for ( i = 0; i < size; i++)
	{
		printf("%d ", arr[i]);
	}
	system("pause");
	return 0;
}

A>交换排序---快速排序

   a>快速排序（Quick Sort)

     算法描述:任取待排序中的某一元素作为基准值,按照该排序码,将待排序集合分割成两个子序列,左边的序列比基准值小,右边的比基准值大.然后对左右子序列重复上述步骤.直到排完为止

   b>快速排序（Quick Sort)动图展示

十大经典排序算法

   c>快速排序代码实现（Quick Sort）

#include "stack.h"
#include<stdio.h>
#include<stdlib.h>
void swap(int *a, int *b){
	int ret = 0;
	ret = *a;
	*a = *b;
	*b = ret;
}
//设定一个基准值,在保证不越界的情况下,从前往后查找比基准值小的元素,找到了然后停下来,若begin和end没有相遇,就交换,相遇了
//就交换begin和数组中基准值所代表的元素
int GetBaseKey(int *array,int left,int right){
	int mid = left + ((right - left) >> 1);
	if (array[left]<array[right]){
		if (array[mid]<array[left])
			return left;
		else if (array[mid]>array[right])
            return right;
	    else
	        return mid;
		
	}
	else
	{
		if (array[mid]>array[left])
		   return left;
	    else if (array[mid] < array[right])
		   return right;
		else
			return mid;
	}
}
//Hoare版本
int partion_hoare(int *array, int left, int right){
	int begin = left;
	int end = right - 1;
	int key_index = GetBaseKey(array, left, right-1);
	swap(&array[key_index], &array[right - 1]);
	int key = array[right-1];
	while (begin<end)
	{
		while ((begin<end)&&array[begin]<key)
		   begin++;
		while ((begin<end)&&array[end]>=key)
		   end--;
		if (begin<end)
		   swap(&array[begin], &array[end]);
		
	}
	if (begin!=right-1)
	   swap(&array[begin], &array[right-1]);
	return begin;
}
//快速排序---挖坑法
int partion_WK(int *array, int left, int right){
	int begin = left;
	int end = right-1;
	int key_index = GetBaseKey(array, left, right - 1);
	swap(&array[key_index], &array[right - 1]);
	int key = array[right - 1];
	while (begin<end)
	{
		while (begin<end&&array[begin]<key)
		  begin++;
		if (begin < end)
		{
			array[end] = array[begin];
			end--;
		}
		while (begin<end&&array[end]>key)
			end--;
		if (begin < end)
		{
			array[begin] = array[end];
			begin++;
		}
	}
	if (begin!=right-1)
	{
		array[begin] = key;
	}
	return begin;
}
//快速排序---前后指针
int partion_P(int *array, int left, int right){
	int pre = left-1;
	int pcur = left;
	int key_index = GetBaseKey(array, left, right - 1);
	swap(&array[key_index], &array[right - 1]);
	int key = array[right - 1];
	while (pcur<right)
	{
		if (array[pcur] < key&&(++pre) != pcur)
			swap(&array[pre], &array[pcur]);
		pcur++;
		
	}
	if ((++pre)!=right-1)
	{
		swap(&array[pre], &array[right-1]);
	}
	return pre;
}
//递归
void QuickSort(int *array,int left,int right){
	if (right-left>1)
	{
		//int base = partion_hoare(array, left, right);
        //int base = partion_WK(array, left, right);
		int base = partion_P(array, left, right);
		QuickSort(array, 0, base);
		QuickSort(array,base+1,right);
	}
}
//非递归,利用栈保存边界
int QuickSort_Nor(int *array,int size){
	int base = 0;
	int left = 0;
	int right = 0;
	SeqStack s;
	StackInit(&s);
	StackPush(&s,size);//保存右边界
	StackPush(&s, 0);//保存左边界
	while (!StackEmpty(&s))
	{
		left = StackTop(&s);
		StackPop(&s);
		right = StackTop(&s);
		StackPop(&s);
		if (left<right)
		{
			base = partion_hoare(array, left, right);
			StackPush(&s, right);//保存右边界
			StackPush(&s, base + 1);//保存左边界
			StackPush(&s, base);
			StackPush(&s, left);
		}
		
	}
	
}
int main(){
	int i = 0;
	int arr[] = {2,0,4,9,3,6,8,7,1,5};
	//int arr[] = {1,2,3,4,5,6};
	int size = sizeof(arr) / sizeof(arr[0]);
	//QuickSort(arr,0,size);
	QuickSort_Nor(arr, size);
	for (i = 0; i < size; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
	system("pause");
	return 0;
}

B>插入排序---直接插入排序

   a>直接插入排序(Insertion sort)

  算法描述:从第一个元素开始,该元素已经排好序,继续取元素与排好序的元素依次进行比较,升序的话插入到比前一个大比后一个小的位置,然后重复上述步骤,直到插完元素为止.

  b>直接插入排序(Insertion sort)动图展示

十大经典排序算法

  c>直接插入排序(Insertion sort)代码实现

#include<stdio.h>
#include<stdlib.h>
//二分查找相比较顺序查找而言,比较的次数比较少.
//插入排序在原本升序排升序,原本逆序排逆序,元素集合接近有序时,直接插入排序效率较高.
//直接插入排序,顺序查找
void insert_sort(int *pArr, int size){
	int i = 0;
	int key = 0;
	int end = 0;
	for ( i = 1; i < size; i++)
	{
		key = pArr[i];
		end = i - 1;
		while (end>=0&&key<pArr[end])
		{
			pArr[end+1]=pArr[end];
			end--;
		}
		pArr[end + 1] = key;
	}
}
//直接插入排序,二分查找
void insert_sort_second(int *pArr, int size){
	int left = 0;
	int right = size-1;
	int mid = 0;
	int i = 0;
	int key = 0;
	for (i = 1; i < size; i++)
	{
		key = pArr[i];
		left = 0;
		right = i - 1;
		//二分查找寻找待插入元素的位置
		while (left <= right)
		{
			mid = (left + right) >> 1;
			if (key<pArr[mid])
			{
				right = mid - 1;
			}
			else
			{
				left = mid + 1;
			}
		}
		//搬移left位置以后的元素
		right = i - 1;
		while (right>=left)
		{
			pArr[right + 1] = pArr[right];
			right--;
		}
		//插入元素
		pArr[left] = key;
    }
}
int main(){
	int i = 0;
	int array[9] = {2,6,4,9,5,8,7,0,1};
	int size = sizeof(array) / sizeof(array[0]);
	//insert_sort(array, size);
	insert_sort_second(array, size);
	for ( i = 0; i < size; i++)
	{
		printf("%d ", array[i]);
	}
	printf("\n");
	system("pause");
	return 0;
}

B>插入排序---希尔排序(直接插入排序的优化)

    a>希尔排序(Shell sort)     

   算法描述:对整个待排序序列进行分组,然后对每一组进行直接插入排序.

                                  十大经典排序算法

  b>希尔排序(Shell sort)动图展示

十大经典排序算法

c>希尔排序(Shell sort)代码实现

#include<stdio.h>
#include<stdlib.h>
void Shell_Sort(int *pArr,int size){
	int i = 0;
	int key = 0;
	int end = 0;
	int gap = 3;
	while (gap > 0)
	{
		for (i = gap; i < size; i++)
		{
			key = pArr[i];
			end = i - gap;
			while (end >= 0 && key<pArr[end])
			{
				pArr[end + gap] = pArr[end];
				end=end-gap;
			}
			pArr[end + gap] = key;
		}
		gap--;
	}
}
int main(){
	int i = 0;
	int array[9] = { 2, 6, 4, 9, 5, 8, 7, 0, 1 };
	int size = sizeof(array) / sizeof(array[0]);
	Shell_Sort(array, size);
	for (i = 0; i < size; i++)
	{
		printf("%d ", array[i]);
	}
	printf("\n");
	system("pause");
	return 0;
}

C>选择排序---直接选择排序   

a>直接选择排序(Insertion sort)

   算法描述:在未排序的序列中找到最小的元素,存放到序列的首位置,找到最大的元素存放到序列的末尾.然后抛开首位和末尾,继续重复该步骤,直到排完为止.

 b>直接选择排序(Insertion sort)动图展示

十大经典排序算法

 c>直接选择排序(Insertion sort)代码实现

#include<stdio.h>
#include<stdlib.h>
void swap(int *a,int *b){
	int ret = 0;
	ret = *a;
	*a = *b;
	*b = ret;
}
void Selection(int *arr,int size){
	int left = 0;
	int right = size - 1;
	int i = 0;
	while (left<right)
	{
		int MinIndex = left;
		int MaxIndex = left;
		for (i = left; i <= right; i++)
		{
			if (arr[MinIndex]>arr[i])
				MinIndex = i;
			if (arr[MaxIndex]<arr[i])
				MaxIndex = i;
		}
		swap(&arr[left],&arr[MinIndex]);
		if (MaxIndex==left)
		{
			MaxIndex = MinIndex;
		}
		swap(&arr[right], &arr[MaxIndex]);
		left++;
		right--;
	}
}
int main(){
	int i = 0;
	int arr[10] = {2,5,4,9,3,6,8,7,1,0};
	int size = sizeof(arr) / sizeof(arr[0]);
	Selection(arr,size);
	for ( i = 0; i < size; i++)
	{
		printf("%d ",arr[i]);
	}
	system("pause");
	return 0;
}
C>选择排序---堆排序   

a>堆排序(Heap sort)

   算法描述:若升序的话,就将堆调成一个大堆,若降序的话,就将堆调成一个小堆.从倒数第一个非叶子节点开始往根遍历,若当前节点的值都大于左右孩子,则不用动,若是小于,就将左右孩子当中最大的节点与当前节点交换,交换后就需要进行向下调整(因为交换会影响大堆结构).重复上述步骤,直到根节点为止.

  b>堆排序(Heap sort)动图展示

十大经典排序算法

  c>堆排序(Heap sort)代码实现

#include "Heap.h"
#include<stdio.h>
#include<stdlib.h>
//向下调整 
void HeapAdjust(int *arrar,int size,int parent){
	int child = parent * 2 + 1;
	while (child<size)
	{
		if ((child + 1)<size&&arrar[child + 1]>arrar[child])
			child += 1;
		if (arrar[parent]<arrar[child])
		{
			swap(&arrar[parent], &arrar[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		  return;
	
	}
	
}
void HeapSort(int arrar[],int size){
	//1,建堆
	int root = ((size - 2) >> 1);
	int end = size - 1;
	for ( ;  root>=0; --root)
	{
		HeapAdjust(arrar, size, root);
	}
	//2,调整
	while (end)
	{
		swap(&arrar[end],&arrar[0]);
		HeapAdjust(arrar, end, 0);
        --end;
	}

}
int main(){
	int arrar[] = { 53, 17, 78, 9, 45, 65, 87, 23, 31 };
	int size = sizeof(arrar) / sizeof(arrar[0]);
	HeapSort(arrar,size);
	for (int i = 0; i <size; i++)
	{
		printf("%d ", arrar[i]);
	}
	system("pause");
	return 0;
}

D>归并排序(Merge Sort)   

   a>归并排序(Merge Sort)      

  算法描述:将待排序的元素序列分为两个长度相等的子序列,对每个子序列进行排序,然后将他们合并成一个序列,合并两个子序列的过程称为二路归并.

   b>归并排序(Merge Sort)动图展示     

十大经典排序算法

  c>归并排序(Merge Sort)代码演示

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<string.h>
#include<assert.h>
//归并
void MergeData(int *arr,int left,int mid,int right,int *temp){
	int temp_index = left;
	int left_L = left;
	int left_R = mid;
	int right_L = mid;
	int right_R = right;
	while (left_L<left_R && right_L<right_R)
	{
		if (arr[left_L]<arr[right_L])
		{
			temp[temp_index++] = arr[left_L++];

		}
		else
		{
			temp[temp_index++] = arr[right_L++];
		}

	}
	while(left_L<left_R)
	{
		temp[temp_index++] = arr[left_L++];
	}
	while (right_L<right_R)
	{
		temp[temp_index++] = arr[right_L++];
	}

}
//分组
//void *memcpy(void*dest, const void *src, size_t n);
//由src指向地址为起始地址的连续n个字节的数据复制到以dest指向地址为起始地址的空间内。
void _MergeSort(int *arr, int left, int right, int *temp){
	if ((right-left)>1)
	{
		int mid = left + ((right-left)>>1);
		_MergeSort(arr,left,mid,temp);
		_MergeSort(arr, mid, right, temp);
		MergeData(arr,left,mid,right,temp);
		memcpy(arr+left,temp+left,sizeof(int)*(right-left));
	}


}
//递归
void MergeSort(int *arr,int size){
	int *temp = (int *)malloc(size*sizeof(arr[0]));
	if (temp==NULL)
	{
		assert(0);
		return;
	}
	_MergeSort(arr,0,size,temp);
	free(temp);
}
//非递归
void MergeSort_Nor(int *arr, int size){
	int *temp = (int *)malloc(size*sizeof(arr[0]));
	if (temp == NULL)
	{
		assert(0);
		return;
	}
	int i = 0;
	int gap = 1;
	while (gap<size)
	{
		for (i = 0; i < size;i+=2*gap){
			int left = i;
			int mid = left + gap;
			int right = mid + gap;
			if (mid>size)
			{
				mid = size;
			}
			if (right>size)
			{
				right = size;
			}
			MergeData(arr, left, mid, right, temp);
		}
		memcpy(arr,temp,size*sizeof(arr[0]));
		gap=gap*2;
	}
	free(temp);
}
int main(){
	int arr[10] = { 2, 0, 4, 9, 3, 6, 8, 7, 1, 5 };
	int size = sizeof(arr) / sizeof(arr[0]);
	MergeSort(arr,size);
	//MergeSort_Nor(arr, size);
	for (int i = 0; i < size; i++)
	{
		printf("%d ", arr[i]);
	}
	system("pause");
	return 0;
}

E>计数排序(鸽巢原理)(Counting Sort)   

   a>计数排序(Counting Sort)        

  算法描述:找到待排序列中最大最小的元素,然后以此确定临时空间的大小,在临时空间中,以待排序列组中元素的大小为下标,该元素出现的次数为该下标对应的元素,根据临时空间的统计结果,重新对元素进行回收.

   b>计数排序(Counting Sort)动图展示     

十大经典排序算法

  c>计数排序(Counting Sort)代码实例

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<string.h>
#include<malloc.h>
int GetMaxValue(int *arr,int size){
	int i = 0;
	int max = arr[0];
	for ( i = 1; i < size; i++)
	{
		if (arr[i]>max)
			max = arr[i];
	}
	return max;

}
int GetMinValue(int *arr, int size){
	int i = 0;
	int min = arr[0];
	for (i = 1; i < size; i++)
	{
		if (arr[i]<min)
			min = arr[i];
	}
	return min;

}
void _Count_Sort(int *arr, int *temp,int size,int ret,int min){
	int i = 0;
	int index = 0;
	//统计个数
	for ( i = 0; i < size; i++)
	{
		temp[arr[i]-min]++;
	}
	//回收,把temp里的数据回收到原空间里
	for ( i = 0; i <ret ; i++)
	{
		while (temp[i]--)
		{
			arr[index++] = i+min;
		}
	}
	free(temp);
}
void Count_Sort(int *arr,int size){
	int max = GetMaxValue(arr,size);
	int min = GetMinValue(arr, size);
	int ret = max - min + 1;
	int *temp = (int *)malloc(ret*sizeof(arr[0]));
	if (temp==NULL)
	{
		assert(0);
		return;
	}
	//memset作用是在一段内存块中填充某个给定的值，它是对较大的结构体或数组进行清零操作的一种最快方法
	memset(temp,0,ret*sizeof(int));
    _Count_Sort(arr,temp,size,ret,min);
}
int main(){
	int i = 0;
	int arr[10] = {3,4,3,2,1,2,6,5,4,7};
	int size = sizeof(arr) / sizeof(arr[0]);
    Count_Sort(arr,size);
	for ( i = 0; i < size; i++)
	{
		printf("%d ", arr[i]);
	}
	system("pause");
	return 0;
}
F>基数排序(Radix Sort)----LSD(底关键码)

   a>基数排序(Radix Sort)    

  算法描述:把待排序中的元素按照低位先排序,然后收集,再按照高位排序,再收集,直至最高位.①,获取序列中的最大数,然后取得其位数,然后利用计数排序的特点,定义10个元素的数组,分别统计以待排序列元素的每一位为数组的下标的元素的个数,然后再定义一个数组存每个的起始地址.开一个辅助空间,放置元素.再回收这些元素.

 b>基数排序(Radix Sort)动图展示

十大经典排序算法

 c>基数排序(Radix Sort)代码展示


#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<malloc.h>
#include<string.h>
//统计最大元素的位数
int GetMaxValue_BitCount(int *arr,int size){
	int i = 0;
	int count = 1;
	int ret = 10;
	for ( i = 0; i < size; i++)
	{
		while (arr[i] >= ret)
		{
			count++;
			ret *= 10;
		}
	}
	return count;
}
void _RadixSort(int *arr,int size,int *temp){
	int Max_BitCount = GetMaxValue_BitCount(arr, size);
	//存每个桶中元素的个数.
	int count[10] = { 0 };
	//存每个桶的起始地址
	int start_Addr[10] = { 0 };
	int i = 0;
	int ret = 1;
	int index = 0;
	while (Max_BitCount)
	{
		//统计个数
		for ( i = 0; i < size; i++)
		{
			count[arr[i] / ret % 10]++;
		}
		//计算地址
		for ( i = 1; i < 10; i++)
		{
			start_Addr[i] = start_Addr[i - 1] + count[i - 1];
		}
		//放置元素到临时空间中
		for (i = 0; i <size; i++){
			int Addr = arr[i]/ret% 10;
			temp[start_Addr[Addr]++] = arr[i];
		}
		//回收元素
		//memcpy函数的功能是从源src所指的内存地址的起始位置开始拷贝n个字节到目标dest所指的内存地址的起始位置中。
		//void *memcpy(void *dest, const void *src, size_t n);
		memcpy(arr,temp,size*sizeof(arr[0]));
		ret *= 10;
		Max_BitCount--;
	}

}
void RadixSort(int *arr,int size){
	int *temp = (int *)malloc(size*sizeof(arr[0]));
	if (temp==NULL)
	{
		assert(0);
		return;
	}
	_RadixSort(arr,size,temp);
	free(temp);
}
int main(){
	int arr[11] = {198,254,378,852,761,554,581,552,605,479,853};
	int size = sizeof(arr) / sizeof(arr[0]);
	RadixSort(arr,size);
	for (int  i = 0; i < size; i++)
	{
		printf("%d ", arr[i]);
	}
	system("pause");
	return 0;
}


相关标签： 十大经典排序算法 选择排序 插入排序 交换排序 归并排序

上一篇： 纯小白系列(一)之PC病毒分析

下一篇： 十大经典排序

推荐阅读