• 使用C语言实现各种排序（总结）

    目录

    1.排序

    （1）排序的稳定性

    （2）内部排序和外部排序

    2.插入排序

    （1）直接插入 排序

    （2）折半插入排序

    （3）希尔排序

    3.冒泡排序

    4.快速排序

    5.简单选择排序

    6.堆排序

    7.归并排序

    8.基数排序

    9.各种排序算法比较总结

    1.排序

    是计算机程序设计中的一种重要的操作，指将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。

    （1）排序的稳定性

    首先假设两个相同的关键字key1=key2，且在排序之前关键字key1在关键字key2之前；若排序之后的结果是关键字key1任然在关键字key2之前，那么排序是稳定的，否则排序不是稳定的。

    （2）内部排序和外部排序

    内部排序：待排序列记录存放在计算机随机存储器中进行的排序过程（也就是在内存中进行的排序）。

    外部排序：待排记录的数量非常的大，导致内存一次性不能读取全部的记录，所以在排序过程中尚需对外存进行访问的排序过程。

    2.插入排序

    （1）直接插入 排序

    算法思想：从待排序列中将一个关键字插入到排序好的有序表中，从而得到一个新的有序表。

    假设待排记录为：49,38,65,97,76,13,27，49²

    直接插入排序
    初始关键字（49）38659776132749²
    i=2（38）（38,49）659776132749²
    i=3（38）（38,49,65）9776132749²
    i=4（38）（38,49,65,97）76132749²
    i=5（76）（38，49，65,76,97）132749²
    i=6（13）（13,38,49,65,76,97）2749²
    i=7（27）（13,27,38,49,65,76,97）49²
    i=8（49²）（13,27,38,49，49²，65,76,97）
    1. #include<stdio.h>
    2. #include<stdlib.h>
    3. #include<math.h>
    4.  
    5. #define MAXSIZE 11
    6.  
    7. typedef int ElemType;
    8.  
    9. void InsertSort(int a[],int n){
    10. 	for(int i=1;i<n;i++){
    11. 		int temp=a[i];
    12. 		int j=i;
    13. 		while(j>0&&temp<a[j-1]){
    14. 			a[j]=a[j-1];
    15. 			j--;
    16. 		}
    17. 		a[j]=temp;
    18. 	}
    19. }
    20. void display(int a[],int n){
    21. 	for(int i=0;i<n;i++){
    22. 		printf("%d\t",a[i]);
    23. 	}
    24. }
    25.  
    26. int main(){
    27. 	int array[MAXSIZE];
    28. 	int n;
    29. 	for(int i=0;i<MAXSIZE;i++){
    30. 		array[i]=0;
    31. 	}
    32. 	printf("请输入待排关键字个数: ");
    33. 	scanf("%d",&n);
    34. 	printf("请输入关键字: ");
    35. 	for(int i=0;i<n;i++){
    36. 		scanf("%d",&array[i]);
    37. 	}
    38. 	InsertSort(array,n);
    39. 	display(array,n);
    40. 	return 0;
    41. }
    42. /*
    43. 49 38 65 97 76 13 27 49
    44. */

    （2）折半插入排序

    思想：之前的直接插入排序从待排记录中取一个关键字，依次与有序表中的关键字进行比较，查找插入的位置，然而折半插入排序利用有序表的特点，进行折半查找，找到待插入关键字的位置。

    1. #include<stdio.h>
    2. #include<stdlib.h>
    3. #include<math.h>
    4.  
    5. #define MAXSIZE 11
    6.  
    7. typedef int ElemType;
    8.  
    9. void BinarySort(int array[],int n){
    10. 	for(int i=1;i<n;i++){
    11. 		int left=0;
    12. 		int right=i-1;
    13. 		int temp=array[i];
    14. 		while(left<=right){
    15. 			int mid=(left+right)/2;
    16. 			if(array[i]>array[mid]){
    17. 				left=mid+1; 
    18. 			}else{
    19. 				right=mid-1;
    20. 			}
    21. 		}
    22. 		for(int j=i;j>=left;j--){
    23. 			array[j]=array[j-1];
    24. 		}
    25. 		array[left]=temp;
    26. 	}
    27. }
    28.  
    29. void display(int a[],int n){
    30. 	for(int i=0;i<n;i++){
    31. 		printf("%d\t",a[i]);
    32. 	}
    33. }
    34.  
    35. int main(){
    36. 	int array[MAXSIZE];
    37. 	int n;
    38. 	for(int i=0;i<MAXSIZE;i++){
    39. 		array[i]=0;
    40. 	}
    41. 	printf("请输入待排关键字个数: ");
    42. 	scanf("%d",&n);
    43. 	printf("请输入关键字: ");
    44. 	for(int i=0;i<n;i++){
    45. 		scanf("%d",&array[i]);
    46. 	}
    47. 	BinarySort(array,n);
    48. 	display(array,n);
    49. 	return 0;
    50. } 
    51. /*
    52. 49 38 65 97 76 13 27 49
    53. */

    （3）希尔排序

    思想：先将整个待排记录序列分割成为若干个子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。

    希尔排序
    初始关键字4938659776132749²554
    第一趟排序（d=5）132749²5544938659776
    第二趟排序（d=2）13449²38274955659776
    第三趟排序（d=1）413273849²4955657697
    1. #include<stdio.h>
    2. #include<stdlib.h>
    3. #include<math.h>
    4.  
    5. #define MAXSIZE 15
    6.  
    7. typedef int ElemType;
    8.  
    9. void ShellSort(int array[],int n){
    10. 	int temp;
    11. 	int d=n/2;
    12. 	while(d){
    13. 		for(int start=d;start<=2*d&&start<n;start++){
    14. 			//这里面是一个直接插入排序 
    15. 			for(int i=start;i<n;i++){
    16. 				temp=array[i];
    17. 				int j=i;
    18. 				while(j>=d&&temp<array[j-d]){
    19. 					array[j]=array[j-d];
    20. 					j-=d;
    21. 				}
    22. 				array[j]=temp;
    23. 			}
    24. 			d=d/2;
    25. 		}
    26. 	}
    27. }
    28.  
    29. void display(int a[],int n){
    30. 	for(int i=0;i<n;i++){
    31. 		printf("%d\t",a[i]);
    32. 	}
    33. }
    34.  
    35. int main(){
    36. 	int array[MAXSIZE];
    37. 	int n;
    38. 	for(int i=0;i<MAXSIZE;i++){
    39. 		array[i]=0;
    40. 	}
    41. 	printf("请输入待排关键字个数: ");
    42. 	scanf("%d",&n);
    43. 	printf("请输入关键字: ");
    44. 	for(int i=0;i<n;i++){
    45. 		scanf("%d",&array[i]);
    46. 	}
    47. 	ShellSort(array,n);
    48. 	display(array,n);
    49. 	return 0;
    50. } 
    51. /*
    52. 49	38	65	97	76	13	27	49	55	4
    53. 49 38 65 97 76 13 27 49 55 4
    54. */

    3.冒泡排序

    思想：首先将第一个关键字和第二个关键字进行比较，若为逆序，则交换两个关键字，然后比较第二个关键字和第三个关键字，直到第n-1个关键字和第n个关键字进行比较，完成一趟冒泡排序，继续后面的操作直到比较到只有一个关键字为止。

    冒泡排序
    初始关键字4938659776132752
    第一趟排序结果38496576132752（97）
    第二趟排序结果384965132752（76,97）
    第三趟排序结果3849132752（65,76,97）
    第四趟排序结果38132749（52,65,76,97）
    第五趟排序结果132738（49,52,65,76,97）
    第六趟排序结果1327（38,49,52,65,76,97）
    第七趟排序结果13（27,38,49,52,65,76,97）
    第八趟排序结果（13，27,38,49,52,65,76,97）
    1. #include<stdio.h>
    2. #include<stdlib.h>
    3. #include<math.h>
    4.  
    5. #define MAXSIZE 15
    6.  
    7. typedef int ElemType;
    8.  
    9. void BubbleSort(int array[],int n){
    10. 	for(int i=0;i<n;i++){
    11. 		for(int j=0;j<n-i-1;j++){
    12. 			if(array[j]>array[j+1]){
    13. 				int temp=array[j];
    14. 				array[j]=array[j+1];
    15. 				array[j+1]=temp;
    16. 			}
    17. 		}
    18. 	}
    19. }
    20.  
    21. void display(int a[],int n){
    22. 	for(int i=0;i<n;i++){
    23. 		printf("%d\t",a[i]);
    24. 	}
    25. }
    26.  
    27. int main(){
    28. 	int array[MAXSIZE];
    29. 	int n;
    30. 	for(int i=0;i<MAXSIZE;i++){
    31. 		array[i]=0;
    32. 	}
    33. 	printf("请输入待排关键字个数: ");
    34. 	scanf("%d",&n);
    35. 	printf("请输入关键字: ");
    36. 	for(int i=0;i<n;i++){
    37. 		scanf("%d",&array[i]);
    38. 	}
    39. 	BubbleSort(array,n);
    40. 	display(array,n);
    41. 	return 0;
    42. } 
    43. /*
    44. 49	38	65	97	76	13	27	49	55	4
    45. 49 38 65 97 76 13 27 49 55 4
    46. */

    4.快速排序

    思想：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均另一部分记录的关键字 小，然后再分别对这两部分记录进行排序，以达到整个记录有序。

    快速排序
    初始关键字49，38，65，97，76，13，27，49²
    第一趟排序结果{27,38,13}49{76,97,65,49²}
    第二趟排序结果{13}27{38}49{49²,65}{76}{97}
    第三趟排序结果1327384949²657697
    1. #include<stdio.h>
    2. #include<stdlib.h>
    3. #include<math.h>
    4.  
    5. #define MAXSIZE 15
    6.  
    7. typedef int ElemType;
    8.  
    9. int Pariation(int array[],int low,int high){
    10. 	int temp=array[low];
    11. 	while(low<high){
    12. 		while(low<high&&temp<array[high]){
    13. 			high--;
    14. 		}
    15. 		if(low<high);
    16. 		array[low]=array[high];
    17. 		while(low<high&&temp>=array[low]){
    18. 			low++;
    19. 		}
    20. 		if(low<high)
    21. 		array[high]=array[low];
    22. 	}
    23. 	array[low]=temp;
    24. 	return low;
    25. }
    26.  
    27. void QuickSort(int array[],int low,int high,int n){
    28. 	if(low<high){
    29. 		int pivo=Pariation(array,low,high);
    30. 		QuickSort(array,low,pivo-1,n);
    31. 		QuickSort(array,pivo+1,high,n);
    32. 	}
    33. }
    34.  
    35. void display(int a[],int n){
    36. 	for(int i=0;i<n;i++){
    37. 		printf("%d\t",a[i]);
    38. 	}
    39. }
    40.  
    41. int main(){
    42. 	int array[MAXSIZE];
    43. 	int n;
    44. 	for(int i=0;i<MAXSIZE;i++){
    45. 		array[i]=0;
    46. 	}
    47. 	printf("请输入待排关键字个数: ");
    48. 	scanf("%d",&n);
    49. 	printf("请输入关键字: ");
    50. 	for(int i=0;i<n;i++){
    51. 		scanf("%d",&array[i]);
    52. 	}
    53. 	QuickSort(array,0,n-1,n);
    54. 	display(array,n);
    55. 	return 0;
    56. } 
    57. /*
    58. 49 38 65 97 76 13 27 49
    59. */

    5.简单选择排序

    思想：每一趟从n-i+1（i=1,2,……，n-1）个记录中选择最小关键字作为有序序列中第i个记录。

    简单选择排序
    初始关键字235133532
    第一趟排序结果523133532
    第二趟排序结果（5,13）233532
    第三趟排序结果（5,13,23）3532
    第四趟排序结果（5,13,23,32）35
    第五趟排序结果（5,13，23,32,35）
    1. #include<stdio.h>
    2. #include<stdlib.h>
    3. #include<math.h>
    4.  
    5. #define MAXSIZE 15
    6.  
    7. typedef int ElemType;
    8.  
    9. int SelectSort(int array[],int n){
    10. 	for(int i=0;i<n;i++){
    11. 		int min_index=i;
    12. 		for(int j=i+1;j<n;j++){
    13. 			if(array[min_index]>array[j]){
    14. 				min_index=j;
    15. 			}
    16. 		}
    17. 		if(min_index!=i){
    18. 			int temp=array[i];
    19. 			array[i]=array[min_index];
    20. 			array[min_index]=temp;
    21. 		}
    22. 	}
    23. }
    24.  
    25.  
    26.  
    27. void display(int a[],int n){
    28. 	for(int i=0;i<n;i++){
    29. 		printf("%d\t",a[i]);
    30. 	}
    31. }
    32.  
    33. int main(){
    34. 	int array[MAXSIZE];
    35. 	int n;
    36. 	for(int i=0;i<MAXSIZE;i++){
    37. 		array[i]=0;
    38. 	}
    39. 	printf("请输入待排关键字个数: ");
    40. 	scanf("%d",&n);
    41. 	printf("请输入关键字: ");
    42. 	for(int i=0;i<n;i++){
    43. 		scanf("%d",&array[i]);
    44. 	}
    45. 	SelectSort(array,n);
    46. 	display(array,n);
    47. 	return 0;
    48. } 
    49. /*
    50. 49 38 65 97 76 13 27 49
    51. */

    6.堆排序

    思想：首相将待排序列调整为堆大堆根（或者小堆根），由于堆顶一定最大的（或者最小的）关键字，所以将堆顶关键字输出；之后继续对剩下的n-1个关键字继续调整为大堆根（或者小堆根），直到剩下的关键字为0.

    1. #include<stdio.h>
    2. #include<stdlib.h>
    3. #include<math.h>
    4.  
    5. #define MAXSIZE 15
    6.  
    7. void PercolateDown( int pa[],int pos,int size)
    8. {
    9. 	int p=pos,c=2*p+1;
    10. 	int temp=pa[p];
    11. 	while(c<size)
    12. 	{
    13. 		if(c+1<size&&pa[c+1]>pa[c])
    14. 		{
    15. 			++c;
    16. 		}
    17. 		if(temp>=pa[c])
    18. 		{
    19. 			break;
    20. 		}else
    21. 		{
    22. 			pa[p]=pa[c];
    23. 			p=c;
    24. 			c=2*p+1;
    25. 		}
    26. 	}
    27. 	pa[p]=temp;
    28. }
    29.  
    30. void PercolateDown(int pa[],int size)
    31. {
    32. 	int p=0,c=2*p+1;
    33. 	int temp=pa[p];
    34. 	while(c<size)
    35. 	{
    36. 		if(c+1<size&&pa[c+1]>pa[c])
    37. 		{
    38. 			++c;
    39. 		}
    40. 		if(temp>pa[c])
    41. 		{
    42. 			break;
    43. 		}else
    44. 		{
    45. 			pa[p]=pa[c];
    46. 			p=c;
    47. 			c=2*p+1;
    48. 		}
    49. 	}
    50. 	pa[p]=temp;
    51. }
    52.  
    53. void BuildHeap(int pa[],int size)
    54. {
    55. 	for(int i=size/2-1;i>=0;i--)
    56. 	{
    57. 		PercolateDown(pa,i,size);
    58. 	}
    59. }
    60.  
    61. void Heapsort(int pa[],int n)
    62. {
    63. 	int temp;
    64. 	BuildHeap(pa,n);
    65. 	for(int i=n-1;i>=0;i--)
    66. 	{
    67. 		temp=pa[0];
    68. 		pa[0]=pa[i];
    69. 		pa[i]=temp;
    70. 		PercolateDown(pa,0,i);
    71. 	}
    72. }
    73.  
    74. void PercolateUp(int pa[],int pos)
    75. {
    76. 	int c=pos,p=(c-1)/2;
    77. 	int temp=pa[c];
    78. 	while(c>0)
    79. 	{
    80. 		if(temp<pa[p])
    81. 		{
    82. 			break;
    83. 		}else
    84. 		{
    85. 			pa[c]=pa[p];
    86. 			c=p;
    87. 			p=(c-1)/2;
    88. 		}
    89. 	}
    90. 	pa[c]=temp;
    91. }
    92.  
    93. void BuildHeap2(int pa[],int size)
    94. {
    95. 	for(int i=0;i<size;i++)
    96. 	{
    97. 		PercolateUp(pa,i);
    98. 	}
    99. }
    100.  
    101. void Heapsort2(int pa[],int n)
    102. {
    103. 	int temp;
    104. 	BuildHeap2(pa,n);
    105. 	for(int i=n-1;i>=0;i--)
    106. 	{
    107. 		temp=pa[0];
    108. 		pa[0]=pa[i];
    109. 		pa[i]=temp;
    110. 		PercolateDown(pa,i);
    111. 		//PercolateDown(pa,i)与BuildHeap2(pa,i)等价;
    112. 	}
    113. }
    114. int main()
    115. {
    116. 	int pa[10]={6,7,89,5,12,4,3,2,35,8};
    117. 	printf("向下调整为大堆根并排序:\n");
    118. 	BuildHeap(pa,10);
    119. 	Heapsort(pa,10);
    120. 	for(int i=0;i<10;i++)
    121. 	{
    122. 		printf("%d\t",pa[i]);
    123. 	}
    124. 	printf("\n");
    125. 	printf("向上调整为大堆根并排序:\n");
    126. 	int pa1[10]={6,7,89,5,12,4,3,2,35,8};
    127. 	BuildHeap2(pa1,10);
    128. 	Heapsort2(pa,10);
    129. 	for(int i=0;i<10;i++)
    130. 	{
    131. 		printf("%d\t",pa[i]);
    132. 	}
    133. 	return 0;
    134. }

    7.归并排序

    思想：假设初始序列为含有n个记录，则可以看成是n个有序的子序列，每个子序列的长度为1，然后进行两两归并，得到[n/2]（向下取整）个长度为2或1的有序子序列；之后再进行两两归并，……，直到归并为长度为n的有序序列为止。

    归并排序
    初始关键字49386597761327
    第一趟归并结果（38,49）（65,97）（13,76）27
    第二趟归并结果（38,49,65,97）（13,27,76）
    第三趟归并结果（13,27,38,49,65,76,97）

    归并排序

    1. #include<stdio.h>
    2. #include<stdlib.h>
    3. #include<math.h>
    4.  
    5. #define MAXSIZE 11
    6.  
    7. typedef int ElemType;
    8. int merge[MAXSIZE];
    9.  
    10. //合并两个有序子序列
    11. void Merge(int merge[],int a[],int left,int right,int middle){
    12. 	int i=left,j=middle+1;
    13. 	int k=left;
    14. 	while(i<=middle&&j<=right){
    15. 		if(a[i]<=a[j]){
    16. 			merge[k++]=a[i++];
    17. 		}else{
    18. 			merge[k++]=a[j++];
    19. 		}
    20. 	}
    21. 	while(i<=middle)merge[k++]=a[i++];
    22. 	while(j<=right)merge[k++]=a[j++];
    23. 	i=0;
    24. 	for(i=left;i<=right;i++)a[i]=merge[i];
    25. }
    26. //合并排序算法
    27. void Mergesort(int a[],int left,int right){
    28. 	if(left<right){
    29. 		int middle=(left+right)>>1;
    30. 		Mergesort(a,left,middle);
    31. 		Mergesort(a,middle+1,right);
    32. 		Merge(merge,a,left,right,middle);
    33.     }
    34. }
    35. void display(int a[],int n){
    36. 	for(int i=0;i<n;i++){
    37. 		printf("%d\t",a[i]);
    38. 	}
    39. }
    40.  
    41. int main(){
    42. 	int array[MAXSIZE];
    43. 	int n;
    44. 	for(int i=0;i<MAXSIZE;i++){
    45. 		array[i]=0;
    46. 	}
    47. 	printf("请输入待排关键字个数: ");
    48. 	scanf("%d",&n);
    49. 	printf("请输入关键字: ");
    50. 	for(int i=0;i<n;i++){
    51. 		scanf("%d",&array[i]);
    52. 	}
    53. 	Mergesort(array,0,n-1);
    54. 	display(array,n);
    55. 	return 0;
    56. } 
    57. /*
    58. 49 38 65 97 76 13 27 49
    59. */

    8.基数排序

    基数排序

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

     

    在这里插入图片描述

    1. #include<iostream>
    2. #include<algorithm>
    3. #include<cstring>
    4. #include<cmath>
    5. #include<queue>
    6. #include<list>
    7. using namespace std;
    8. const int maxx=10;
    9. int pa[maxx];
    10. int n;
    11. template<class T>
    12. class Queue{
    13. 	private:
    14. 		list<T>q;
    15. 	public:
    16. 		int Size(){return q.size();}
    17. 		int Empty(){return q.empty();}
    18. 		void Clear(){return q.clear();}
    19. 		void Push(const T&item){q.push_back(item);}
    20. 		T Pop(){T item=q.front();q.pop_front();return item;}
    21. };
    22. void Radixsort(int n){
    23. 	Queue<int>q[10];//10个箱子
    24. 	int base=1,flag=1,k;
    25. 	while(flag){
    26. 		for(int i=0;i<n;i++){//分配
    27. 			k=(pa[i]/base)%10;
    28. 			q[k].Push(pa[i]);
    29. 		}
    30. 		base*=10;//晋级到更高一位
    31. 		flag=0;//每趟收集前，令flag=0
    32. 		int i=0;
    33. 		for(k=0;k<10;k++){//收集
    34. 			while(!q[k].Empty()){
    35. 				pa[i++]=q[k].Pop();
    36. 				if(pa[i-1]/base!=0&&flag==0){
    37. 					flag=1;//还有更大的数位
    38. 				}
    39. 			}
    40. 		}
    41. 	}
    42. }
    43. int main(){
    44. 	while(scanf("%d",&n)!=EOF){
    45. 		for(int i=0;i<n;i++){
    46. 			scanf("%d",&pa[i]);
    47. 		}
    48. 		Radixsort(n);
    49. 		for(int i=0;i<n;i++){
    50. 			cout<<pa[i]<<" ";
    51. 		}
    52. 	}
    53. 	return 0;
    54. }

    9.各种排序算法比较总结

    排序算法 比较
    排序方法平均时间最坏情况辅助空间稳定性
    直接插入排序O(n²)O(n²)O(1)稳定
    折半插入排序O(n²)O(n²)O(1)稳定
    希尔排序不稳定
    简单选择排序O(n²)O(n²)O(1)稳定
    快速排序O(nlogn)O(n²)O(logn)不稳定
    堆排序O(nlogn)O(nlogn)O(1)不稳定
    归并排序O(nlogn)G(nlogn)O(n)稳定
    基数排序O(d(n+rd))O(d(n+rd))O(rd)稳定

    参考数据：《数据结构》清华大学

  • 相关阅读:
    python字典、列表排序，从简单到复杂
    Redis 列表操作实战（全）
    【算法-动态规划】斐波那契第 n 项
    Ansys Zemax | 解像力仿真设计
    QT_day3
    微信小程序如何关联视频号直播
    【Angular】06表单控件与表单验证
    Spring Task定时任务(定期删除token和无效文件)
    [附源码]计算机毕业设计JAVAjsp大学生就业信息检索系统
    基于YOLO算法的单目相机2D测量（工件尺寸和物体尺寸）三
  • 原文地址：https://blog.csdn.net/Keep_Trying_Go/article/details/126692841