10种排序算法总结-（c语言实现与动画演示）

算法分类

十种常见排序算法可以分为两大类：

比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。
非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。

稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。

不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。

1.冒泡排序：

#include<stdio.h>
#include<malloc.h>
void BubbleSort(int *arr,int size)
{
    int i = 0;
    int j = 0;
    for(i=0;i<size-1;i++)
	{
        for(j=0;j<size-i-1;j++)
		{
            if(arr[j]>arr[j+1])
			{
                int tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
            }
        }
    }
}
int main()
{
	int a[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
	int  len=sizeof(a)/sizeof(a[0]);
	BubbleSort(a,len);
 
	for(int i=0;i<len;i++)
	printf("%d--",a[i]);
	
}

2.选择排序

#include<stdio.h> 
void swap(int* a,int* b)//交换函数 
{
	int tem=*a;
	*a=*b;
	*b=tem;
}
 
void selectionSort(int *arr, int n) //选择排序函数 
{
    for (int i = 0; i < n - 1; i++) 
	{
        int minIndex = i;
        for (int j = i + 1; j < n; j++)
		{
            if (arr[j] < arr[minIndex]) 
			{
                minIndex = j;
            }
        }
        swap(&arr[minIndex],&arr[i]);
    }
}
 
int main()
{
	int arr[] = {3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
    int n = sizeof(arr) / sizeof(arr[0]);
    selectionSort(arr, n);
    for(int i=0;i<n;i++)
    printf("%d--",arr[i]);
}

3.插入排序

#include<stdio.h>
#include<stdlib.h>
void swap(int* a,int* b)
{
	int tem=*a;
	*a=*b;
	*b=tem;
}
void InsertSort(int *arr,int n)
{
	for(int i=1;i<n;i++)
	{
	if(arr[i]<arr[i-1])
	{
		swap(&arr[i],&arr[i-1]);
		for(int j=i-1;j>0&&arr[j]<arr[j-1];j--)
		{
			swap(&arr[j],&arr[j-1]);
		}
	}
	}
}
int main()
{
	int arr[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
	int n = sizeof(arr) / sizeof(arr[0]);
	InsertSort(arr,n);
	for(int i=0;i<n;++i)
	{
		printf("%d--",arr[i]);
	}
 } 

4.希尔排序

#include<stdio.h>
//希尔排序
void ShellSort(int *arr,int n){
	int d,i,j,temp;
	for(d=n/2;d>=1;d=d/2){
		for(i=d;i<n;i++){//增量 
			if(arr[i]<arr[i-d]){
				temp=arr[i];
				for(j=i-d;j>=0&&temp<arr[j];j-=d){
					arr[j+d]=arr[j];
				}
				arr[j+d]=temp;
			}
		}
	}
}
 
int main()
{
	int arr[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
	int n = sizeof(arr) / sizeof(arr[0]);
	ShellSort(arr,n);
	for(int i=0;i<n;++i)
	{
		printf("%d--",arr[i]);
	}
 } 

5.归并排序

#include<stdio.h>
void merge(int arr[], int left[], int size_left, int right[], int size_right) 
{  
    int i = 0, j = 0, k = 0;  
    while (i < size_left && j < size_right) 
	{  
        if (left[i] <= right[j])
		{  
            arr[k++] = left[i++];  
        } 
		else 
		{  
            arr[k++] = right[j++];  
        }  
    }  
 
    // 复制剩余的元素  
    while (i < size_left)
    {  
        arr[k++] = left[i++];  
    }  
    while (j < size_right) 
    {  
        arr[k++] = right[j++];  
    }  
}  
 
// 归并排序  
void mergeSort(int *arr, int n) {  
    if (n <= 1) return;  
    int mid = n / 2;  
    int left[mid];  
    int right[n - mid];  
 
  
    // 复制数据到临时数组  
    for (int i = 0; i < mid; i++) 
	{  
        left[i] = arr[i];  
    }  
 
    for (int i = mid; i < n; i++) 
	{  
        right[i - mid] = arr[i];  
    }  
    // 递归排序左半部分和右半部分  
    mergeSort(left, mid);  
    mergeSort(right, n - mid);  
    
    // 合并两个已排序的数组  
    merge(arr, left, mid, right, n - mid);  
 
}  
 
int main()
{
	int arr[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
	int n = sizeof(arr) / sizeof(arr[0]);
	mergeSort(arr, n);  
	for(int i=0;i<n;++i)
	{
		printf("%d--",arr[i]);
	}
} 

6.快速排序

#include<stdio.h>
#include<stdlib.h>
 
void swap(int* a,int* b)
{
	int tem=*a;
	*a=*b;
	*b=tem;
}
 
 
int Partition(int* arr,int low ,int high)
{
	int pk=arr[low];
	while(low<high)
	{
		while(low<high&&arr[high]>=pk)
		high--;
		arr[low]=arr[high];
		while(low<high&&arr[low]<pk)
		low++;
		arr[high]=arr[low];
	}
	arr[low]=pk;
	return low;
}
void QuickSort(int* arr,int low,int high)
{
	if(low<high)
	{
		int pkloc=Partition(arr,low,high);//找到分界线 
		QuickSort(arr,low,pkloc-1);
		QuickSort(arr,pkloc+1,high); 
	}
}
int main()
{
	int arr[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
	int n = sizeof(arr) / sizeof(arr[0]);
	QuickSort(arr,0,n-1);
	for(int i=0;i<n;++i)
	{
		printf("%d--",arr[i]);
	}
 }

7.堆排序

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
void siftDown(int* heap,int n,int p);
void swap(int* a,int* b)
{
	int tem=*a;
	*a=*b;
	*b=tem;
}
int RemoveMinKey(int* heap,int n)
{
	int key =heap[0];
	heap[0]=heap[n];
	siftDown(heap,n,0);
	return key;
}
void siftDown(int* heap,int n,int p)
{
	int i=p;//i
	int j=2*i+1;//左子树 
	while(j<n)//不超出范围 
	{
		if(j<n-1&&heap[j]>heap[j+1])//j为左子树，+1为右子树 
		j++;
		if(heap[i]<=heap[j])
		break;
		else
		{
			swap(&heap[j],&heap[i]);
			i=j;
			j=2*i+1;
		}
	}
}
void HeapSort(int* arr,int n) 
{
	int *heap=(int*)malloc(sizeof(int)*n);
	for(int i=0;i<n;++i)
	{
		heap[i]=arr[i];
	}
	int curpos=n/2-1;
	while(curpos>=0)
	{
		siftDown(heap,n,curpos);
		curpos--;
	}
	for(int i=0;i<n;++i)
	{
		//printf("%d  ",heap[i]);
		arr[i]=RemoveMinKey(heap,n-i-1);
		
	}
	//printf("\n");
	free(heap);
	heap=NULL;
	
}
 
int main()
{
	int arr[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
	int n = sizeof(arr) / sizeof(arr[0]);
	HeapSort(arr,n);
	for(int i=0;i<n;++i)
	{
		printf("%d--",arr[i]);
	}
 }

8.计数排序

#include <stdio.h>  
#include<malloc.h>
// 计数排序函数  
void countingSort(int arr[], int n) 
{  
    // 找到数组中的最大值  
    int max = arr[0];  
    for (int i = 1; i < n; i++)
	{  
        if (arr[i] > max) 
		{  
            max = arr[i];  
        }  
    }  
 
    // 初始化计数数组  
    int *count = (int *)malloc(sizeof(int) * (max + 1));
	for(int i=0;i<=max;i++)
		count[i]=0; 
		
    // 计算每个元素的计数  
    for (int i = 0; i < n; i++) 
	{
        count[arr[i]]++; 
    }  
	
	int output=0;//计数 
	for(int i=0;i<=max;i++)//循环每个计数盘子 
	{
		while(count[i]>0)//当盘子中数的个数大于0时，赋值到arr，并减少一个 
		{
		arr[output++]=i;//赋值给arr 
		count[i]--;
		}	
	}
    free(count);  
}  
 
int main()
{
	int arr[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
	int n = sizeof(arr) / sizeof(arr[0]);
	countingSort(arr,n);
	for(int i=0;i<n;++i)
	{
		printf("%d--",arr[i]);
	}
 } 

9.基数排序

#include <stdio.h>  
#include<malloc.h>
//基数排序
void RadixSort(int* arr, int n)
{
	int max = arr[0];
	int base = 1;
 
	//找出数组中的最大值
	for (int i = 0; i < n; i++)
	{
		if (arr[i] > max)
		{
			max = arr[i];
		}
	}
 
	//临时存放数组元素的空间
	int* tmp = (int*)malloc(sizeof(int)*n);
 
	//循环次数为最大数的位数
	while (max / base > 0)
	{
		//定义十个桶，桶里面装的不是数据本身，而是每一轮排序对应（十、白、千...）位的个数
		//统计每个桶里面装几个数
		int bucket[10] = { 0 };
		for (int i = 0; i < n; i++)
		{
			//arr[i] / base % 10可以取到个位、十位、百位对应的数字
			bucket[arr[i] / base % 10]++;
		}
		//循环结束就已经统计好了本轮每个桶里面应该装几个数
 
 
		//将桶里面的元素依次累加起来，就可以知道元素存放在临时数组中的位置
		for (int i = 1; i < 10; i++)
		{
			bucket[i] += bucket[i - 1];
		}
		//循环结束现在桶中就存放的是每个元素应该存放到临时数组的位置
 
 
		//开始放数到临时数组tmp
		for (int i = n - 1; i >= 0; i--)
		{
			tmp[bucket[arr[i] / base % 10] - 1] = arr[i];
			bucket[arr[i] / base % 10]--;
		}
 
		//把临时数组里面的数拷贝回去
		for (int i = 0; i < n; i++)
		{
			arr[i] = tmp[i];
		}
		base *= 10;
	}
	free(tmp);
}
 
 
int main()
{
	int arr[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
	int n = sizeof(arr) / sizeof(arr[0]);
	RadixSort(arr,n);
	for(int i=0;i<n;++i)
	{
		printf("%d--",arr[i]);
	}
 } 

参考：https://www.cnblogs.com/onepixel/p/7674659.html