当前位置：文档之家 › c语言各种排序法详解

c语言各种排序法详解

  • 格式：docx
  • 大小：20.87 KB
  • 文档页数：8

一插入排序1.1 直接插入排序基本思想：每次将一个待排序额记录按其关键码的大小插入到一个已经排好序的有序序列中，直到全部记录排好序。

图解：代码实现：[cpp]view plaincopy1.//直接顺序排序2.void InsertSort(int r[],int n)3.{4.for(int i=2;i<n;i++)5.{6.r[0]=r[i];//设置哨兵7.for(int j=i-1;r[0]<r[j];j--)//寻找插入位置8.r[j+1]=r[j];//记录后移9.r[j+1]=r[0];10.}11.for(int k=1;k<n;k++)12.cout<<r[k]<<"";13.cout<<"\n";14.}1.2 希尔排序基本思想是：先将整个待排序记录序列分割成若干个子序列，在在序列内分别进行直接插入排序，待整个序列基本有序时，再对全体记录进行一次直接插入排序。

图解：代码实现：[cpp]view plaincopy1.<spanstyle="font-size:14px;">//希尔排序2.void ShellSort(int r[],int n)3.{4.int i;5.int d;6.int j;7.for(d=n/2;d>=1;d=d/2)//以增量为d进行直接插入排序8.{9.for(i=d+1;i<n;i++)10.{11.r[0]=r[i];//暂存被插入记录12.for(j=i-d;j>0&&r[0]<r[j];j=j-d)13.r[j+d]=r[j];//记录后移d个位置14.r[j+d]=r[0];15.}16.}17.for(i=1;i<n;i++)18.cout<<r[i]<<"";19.cout<<"\n";20.}</span>二交换排序2.1 起泡排序起泡排序是交换排序中最简单的排序方法，其基本思想是：两两比较相邻记录的关键码，如果反序则交换，直到没有反序的记录为止。

图解：代码实现：[cpp]view plaincopy1.<spanstyle="font-size:14px;">//起泡排序2.void BubbleSort(int r[],int n)3.{4.int temp;5.int exchange;6.int bound;7.exchange=n-1;//第一趟起泡排序的范围是r[0]到r[n-1]8.while(exchange)//仅当上一趟排序有记录交换才进行本趟排序9.{10.bound=exchange;11.exchange=0;12.for(int j=0;j<bound;j++)//一趟起泡排序13.if(r[j]>r[j+1])14.{15.temp=r[j];16.r[j]=r[j+1];17.r[j+1]=temp;18.exchange=j;//记录每一次发生记录交换的位置19.}20.}21.for(int i=0;i<n;i++)22.cout<<r[i]<<"";23.cout<<"\n";24.}</span>2.2快速排序基本思想:通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

图解：代码实现：[cpp]view plaincopy1.//快速排序一次划分2.int Partition(int r[],int first,int end)3.{4.int i=first;//初始化5.int j=end;6.int temp;7.while(i<j)8.{9.while(i<j&&r[i]<=r[j])10.j--;//右侧扫描11.if(i<j)12.{13.temp=r[i];//将较小记录交换到前面14.r[i]=r[j];15.r[j]=temp;16.i++;17.}18.while(i<j&&r[i]<=r[j])19.i++;//左侧扫描20.if(i<j)21.{22.temp=r[j];23.r[j]=r[i];24.r[i]=temp;//将较大记录交换到后面25.j--;26.}27.}28.return i;//i为轴值记录的最终位置29.}30.//快速排序31.void QuickSort(int r[],int first,int end)32.{33.if(first<end)34.{//递归结束35.int pivot=Partition(r,first,end);//一次划分36.QuickSort(r,first,pivot-1);//递归地对左侧子序列进行快速排序37.QuickSort(r,pivot+1,end);//递归地对右侧子序列进行快速排序38.}39.}三选择排序3.1 简单选择排序基本思想：设所排序序列的记录个数为n。

i取1,2,…,n-1,从所有n-i+1个记录（Ri,Ri+1,…,Rn）中找出排序码最小的记录，与第i个记录交换。

执行n-1趟后就完成了记录序列的排序。

图解：代码实现：[cpp]view plaincopy1.//简单选择排序2.void SelectSort(int r[],int n)3.{4.int i;5.int j;6.int index;7.int temp;8.for(i=0;i<n-1;i++)//对n个记录进行n-1趟简单选择排序9.{10.index=i;11.for(j=i+1;j<n;j++)//在无序区中选取最小记录12.if(r[j]<r[index])13.index=j;14.if(index!=i)15.{16.temp=r[i];17.r[i]=r[index];18.r[index]=temp;19.}20.}21.for(i=0;i<n;i++)22.cout<<r[i]<<"";23.cout<<"\n";24.}3.2 堆排序堆的定义堆是具有下列性质的完全二叉树：每个结点的值都小于或等于其左右孩子结点的值（小根堆）；或者每个结点的值都大于或等于其左右孩子结点的值（大根堆）。

大根堆和小根堆：根结点（亦称为堆顶）的关键字是堆里所有结点关键字中最小者的堆称为小根堆，又称最小堆。

根结点（亦称为堆顶）的关键字是堆里所有结点关键字中最大者，称为大根堆，又称最大堆。

注意：①堆中任一子树亦是堆。

②以上讨论的堆实际上是二叉堆（BinaryHeap），类似地可定义k叉堆。

假设当前要筛选结点的编号为k，堆中最后一个结点的编号为m，并且结点k的左右子树均是堆（即r[k+1] ~ r[m]满足堆的条件），则筛选算法用伪代码可描述为：具体的筛选代码如下：[cpp]view plaincopy1.//筛选法调整堆2.void Sift(int r[],int k,int m)3.{4.int i;5.int j;6.int temp;7.i=k;8.j=2*i+1;//置i为要筛的结点，j为i的左孩子9.while(j<=m)//筛选还没有进行到叶子10.{11.if(j<m&&r[j]<r[j+1])12.j++;//比较i的左右孩子，j为较大者13.if(r[i]>r[j])break;//根结点已经大于左右孩子中的较大者14.else15.{16.temp=r[i];17.r[i]=r[j];18.r[j]=temp;//将根结点与结点j交换19.i=j;20.j=2*i+1;//被筛结点位于原来结点j的位置21.}22.}23.}堆排序堆排序的基本思想是：首先将待排序的记录序列构造成一个堆，此时，选出了堆中所有记录的最大者即堆顶记录，然后将它从堆中移走（通常将堆顶记录和堆中最后一个记录交换），并将剩余的记录再调整成堆，这样又找出了次大的记录，以此类推，直到堆中只有一个记录为止。

（1）用大根堆排序的基本思想①先将初始文件R[1..n]建成一个大根堆，此堆为初始的无序区②再将关键字最大的记录R[1]（即堆顶）和无序区的最后一个记录R[n]交换，由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key③由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。

然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系R[1..n-2].keys≤R[n-1..n].keys，同样要将R[1..n-2]调整为堆。

……直到无序区只有一个元素为止。

（2）大根堆排序算法的基本操作：①初始化操作：将R[1..n]构造为初始堆；②每一趟排序的基本操作：将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换，然后将新的无序区调整为堆（亦称重建堆）。

注意：①只需做n-1趟排序，选出较大的n-1个关键字即可以使得文件递增有序。

②用小根堆排序与利用大根堆类似，只不过其排序结果是递减有序的。

堆排序和直接选择排序相反：在任何时刻堆排序中无序区总是在有序区之前，且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止代码实现：[cpp]view plaincopy1.//堆排序2.void HeapSort(int r[],int n)3.{4.int i;5.int temp;6.for(i=n/2;i>=0;i--)//初始建堆，从最后一个非终端结点至根结点7.Sift(r,i,n);8.for(i=n-1;i>0;i--)//重复执行移走堆顶及重建堆的操作9.{10.temp=r[i];11.r[i]=r[0];12.r[0]=temp;13.Sift(r,0,i-1);14.}15.for(i=0;i<n;i++)16.cout<<r[i]<<"";17.cout<<"\n";18.}四归并排序二路归并排序基本思想：将若干个有序序列进行两两归并，直至所有待排序记录都在一个有序序列为止。

合集下载

C语言数组的五种简单排序，选择法排序，冒泡法排序、交换法排序、插入法排序、折半法排序

C语言数组的五种简单排序，选择法排序，冒泡法排序、交换法排序、插入法排序、折半法排序

C语⾔数组的五种简单排序，选择法排序，冒泡法排序、交换法排序、插⼊法排序、折半法排序⽂章⽬录1、选择法排序选择法排序是指每次选择索要排序的数组中的最⼩值（这⾥是由⼩到⼤排序，如果是由⼤到⼩排序则需要选择最⼤值）的数组元素，将这些数组元素的值与前⾯没有进⾏排序的数组元素值进⾏互换代码实现需要注意的是：声明⼀个数组和两个整形变量，数组⽤于存储输⼊的数字，⽽整形变量⽤于存储最⼩的数组元素的数值与该元素的位置，在我的代码中实现为a[] temp position。

代码具体如下#include<stdio.h>int main(){int m,n,k;printf("please input the length of the array:");scanf("%d",&k);int a[k];int temp;int position;printf("please input the number of the array:\n");for(m=0;m<k;m++){printf("a[%d]=",m+1);scanf("%d",&a[m]);}/*从⼩到⼤排序*/for(m=0;m<k-1;m++){temp=a[m]; //设置当前的值为最⼩值position=m; //记录当前的位置for(n=m+1;n<k;n++){if(a[n]<temp){temp=a[n]; //如果找到⽐当前的还要⼩的数值，则更换最⼩的数值与位置position=n;}}a[position]=a[m];a[m]=temp;}for(m=0;m<k;m++){printf("%d\t",a[m]);}return 0;}结果如下2、冒泡法排序冒泡法排序就是值在排序时，每次⽐较数组中相邻的两个数组元素的值，将⽐较⼩的（从⼩到⼤排序算法，如果是从⼤到⼩排序算法就是将较⼤的数排在较⼩的数前⾯）排在⽐较⼤的前⾯在代码实现的过程中：声明⼀个数组与⼀个整型变量，数组⽤于存放数据元素，整型变量⽤于交换时作为中间变量。

C语言--常见排序算法

C语言--常见排序算法

25 1 i k
49
2 j 49
08
0
25* 3 49 25
16 4
21
5
08
25
25*
16
21
i k 49
j 25* 25
08
25
25*
16
21
算法实例：
1.1.5 选择排序
49 2
08 0
25 1 i
25* 3
16 4 k
21 5 j 21 16
k 指示当前序列中最小者
算法实现：
08 5 temp
16 21 25 25* 49 08 0 1 2 3 4 5
算法实现：
1.1.3 直接插入排序
void InsertSort (int r[ ], int n ) { // 假设关键字为整型，放在向量r[]中 int i, j, temp; for (i = 1;i< n;i++ ) { temp = r[i]; for(j = i;j>0;j- -) {//从后向前顺序比较，并依次后移 if ( temp < r[j-1] ) r[j] = r[j-1]; else break; } r[j] = temp; } }
输入n 个数给a[1] 到 a[n]
for j=1 to n-1
for i=1 to n-j
真 a[i]>a[i+1]
a[i]a[i+1]
输出a[1] 到 a[n]
main() { int a[11],i,j,t; printf("Input 10 numbers:\n"); for(i=1;i<11;i++) scanf("%d",&a[i]); printf("\n"); 假 for(j=1;j<=9;j++) for(i=1;i<=10-j;i++) if(a[i]>a[i+1]) {t=a[i]; a[i]=a[i+1]; a[i+1]=t;} printf("The sorted numbers:\n"); for(i=1;i<11;i++) printf("%d ",a[i]); }
c语言中排序的各种方法解析

c语言中排序的各种方法解析

c语言中排序的各种方法解析一、引言在计算机编程中，排序是一个重要的操作，它按照一定的顺序排列数据元素，使得数据元素按照从小到大的顺序排列。

在C语言中，有多种方法可以实现排序，包括冒泡排序、选择排序、插入排序、快速排序、归并排序等。

这些排序算法都有各自的优缺点，适合不同的应用场景。

二、冒泡排序冒泡排序是一种简单的排序算法，它重复地遍历要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。

遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

算法步骤：1. 比较相邻的元素。

如果第一个比第二个大（升序），就交换它们两个。

2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。

这步做完后，最后的元素会是最大的数。

3. 针对所有的元素重复以上的步骤，除了最后一个。

4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

三、选择排序选择排序是一种简单直观的排序算法。

它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

算法步骤：1. 在未排序序列中找到最小元素，存放到排序序列的起始位置。

2. 再从剩余未排序元素中继续寻找最小元素，然后放到已排序序列的末尾。

3. 以此类推，直到所有元素均排序完毕。

四、插入排序插入排序的工作方式是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

插入排序在实现上通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

五、快速排序快速排序使用了分治的原则，它在每一层划分都比前面方法有所改进和精进，当切分到两边的子序列长度都大于某个值时，或者一个大于一个小于这个值时再进行交换的操作来结束此层的递归过程。

这层的结果又成为下一层的两个子数组来处理，最后就得到递归式的最终结果。

使用C语言实现12种排序方法

使用C语言实现12种排序方法

使⽤C语⾔实现12种排序⽅法⽬录1.冒泡排序2.插⼊排序3.折半插⼊排序4.希尔排序5.选择排序6.鸡尾酒排序7.堆排序8.快速排序9.归并排序10.计数排序11.桶排序12.基数排序1.冒泡排序思路：⽐较相邻的两个数字，如果前⼀个数字⼤，那么就交换两个数字，直到有序。

时间复杂度O(n^2)，稳定性：这是⼀种稳定的算法。

代码实现：void bubble_sort(int arr[],size_t len){size_t i,j;for(i=0;i<len;i++){bool hasSwap = false; //优化，判断数组是否已经有序，如果有序可以提前退出循环for(j=1;j<len-i;j++){ //这⾥j<len-i是因为最后⾯的肯定都是最⼤的，不需要多进⾏⽐较if(arr[j-1]>arr[j]){ //如果前⼀个⽐后⼀个⼤swap(&arr[j-1],&arr[j]); //交换两个数据hasSwap = true;}}if(!hasSwap){break;}}}2.插⼊排序思路：把⼀个数字插⼊⼀个有序的序列中，使之仍然保持有序，如对于需要我们进⾏排序的数组，我们可以使它的前i个数字有序，然后再插⼊i+1个数字，插⼊到合适的位置使之仍然保持有序，直到所有的数字有序。

时间复杂度：O(n^2) 稳定性：稳定的算法代码实现：void insert_sort(int arr[],int len){int i,j;for(i=1;i<len;i++){int key = arr[i]; //记录当前需要插⼊的数据for(j= i-1;i>=0&&arr[j]>key;j--){ //找到插⼊的位置arr[j+1] = arr[j]; //把需要插⼊的元素后⾯的元素往后移}arr[j+1] = key; //插⼊该元素}}3.折半插⼊排序思路：本质上是插⼊排序，但是通过半分查找法找到插⼊的位置，让效率稍微快⼀点。