zdw

用户名：18075654465

访问量：16104

签　名：

抬头ctrl+c，低头ctrl+v，摇头ctrl+z；

等　　级
排　　名	535
经　　验	4443
参赛次数	0
文章发表	12
年　　龄	0
在职情况	学生
学　　校	四川轻化工大学
专　　业	软件工程

　　自我简介：

TA的其他文章

排序算法总结之-冒泡、选择、插入、希尔、归并排序（含C++代码实现）
浏览：686

你可能喜欢

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言训练-8除不尽的数（C语言代码）暴力解法，答案只有一个，直接输出就好了

排序算法总结之-冒泡、选择、插入、希尔、归并排序（含C++代码实现）

　　作者: zdw　　　　发表时间：2019-07-27 20:26:07 浏览：686　|　评论：0　

**这个链接里面是排序算法的一些说明，没看的可以去看看
 [排序算法总结（前言）](https://blog.dotcpp.com/a/60910 "排序算法总结（前言）")**

------------

#### 1、冒泡排序（Bubble Sort）

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

#####１.１ 算法描述
1. 比较相邻的元素。如果第一个比第二个大，就交换它们两个；

1. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
1. 针对所有的元素重复以上的步骤，除了最后一个；

1. 重复步骤1~3，直到排序完成。

#####１.２ 代码实现
	void BubbleSort(int arr[],int n)
	{
		int i,j;//i控制趟数，j控制每趟比较
		for (i= 0; i < n; i++)//n为数组的长度
    	{
			for (int j = 0; j < n - 1 - i; j++)
			{
				if (arr[j + 1] < arr[j])//大的向后移
				{
					int temp = arr[j + 1];
        	    	arr[j + 1] = arr[j];
           		 arr[j] = temp;
				 }
			}
		}
	}
##### 1.3 算法分析

**最佳情况：T(n) = O(n)　　最差情况：T(n) = O(n2)　　平均情况：T(n) = O(n2)**

------------

#### 2、选择排序（Selection Sort）

表现最稳定的排序算法之一，因为无论什么数据进去都是O(n2)的时间复杂度，用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。是一种简单直观的排序算法。

##### 2.1 算法描述

1. 首先在未排序序列中找到最小（大）元素；
   
   1. 存放到排序序列的起始位置；
   1. 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
   
   1. 重复1~3，直到所有元素均排序完毕。

------------

##### 2.２ 代码实现
	void SelectSort(int arr[],int n)
	{
		int i,j;
    	for( i = 0; i < ｎ; i++) 
		{
			int minIndex = i;
			for(int j = i+1; j < n; j++)
			{
				if(arr[j]<arr[minIndex])//找到最小的数
				{
           	 	minIndex = j; //将最小数的索引保存
            	}
            	int temp = arr[minIndex];//把最小的数与i进行交换
            	arr[minIndex] = arr[i];
            	arr[i] = temp;
			}
		}
	}

##### 2.3 算法分析

**最佳情况：T(n) = O(n2)  最差情况：T(n) = O(n2)  平均情况：T(n) = O(n2)**

------------

#### 3、插入排序（Insertion Sort）

插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

##### 3.1 算法描述

一般来说，插入排序都采用in-place在数组上实现。
具体算法描述如下：

1. 从第一个元素开始，该元素可以认为已经被排序；
  
  1. 取出下一个元素，在已经排序的元素序列中从后向前扫描；
  1. 如果该元素（已排序）大于新元素，将该元素移到下一位置；

1. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
  
  1. 将新元素插入到该位置后；

1. 重复步骤2~5。

------------

##### 3.2 代码实现

void InsertSort(int arr[],int k)
    {
    	if(k==0)
    		return ;
    	InsertSort(arr,k-1);
    	int x=arr[k],index=k-1;
    	while(index>-1&&x<arr[index])
    	{
    		arr[index+1]=arr[index];
    		index--;
    	}
    	arr[index+1]=x;
    }

##### 3.3 算法分析

**最佳情况：T(n) = O(n)   最坏情况：T(n) = O(n2)   平均情况：T(n) = O(n2)**

------------

#### 4、希尔排序（Shell Sort）

希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。它与插入排序的不同之处在于，它会优先比较距离较远的元素。

希尔排序是按下标进行增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

##### 4.1 算法描述

希尔排序的基本步骤，选择增量interval=n/2，缩小增量继续以interval = interval/2的方式，这种增量选择我们可以用一个序列来表示，{n/2,(n/2)/2...1}，称为增量序列。**PS：希尔排序的增量序列的选择与证明是个数学难题，我们选择的这个增量序列是比较常用的，也是希尔建议的增量，但其实这个增量序列不是最优的。**

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：
  1. 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
  
  1. 按增量序列个数k，对序列进行k 趟排序；
  1. 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

------------

##### 4.2 代码实现

void shellsort(int arr[],int n)
	{
		int interval,i;
		for(interval=n/2;interval>0;interval/=2)
		{
			for(i=interval;i<n;i++)//这里会对每个组同时进行插入排序 
			{
				int target=arr[i];
				int k=i-interval;
				while(k>-1&&target<arr[k])
				{
					arr[k+interval]=arr[k];
					k-=interval;
				}
				arr[k+interval]=target;
			}
		}
	}

##### 4.3 算法分析

**最佳情况：T(n) = O(nlog2 n)  最坏情况：T(n) = O(nlog2 n)  平均情况：T(n) =O(nlog2n)**

------------

#### 5、归并排序（Merge Sort）

和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(nlogn）的时间复杂度。**代价是需要额外的内存空间。**

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；**即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。**

##### 5.1 算法描述
1. 把长度为n的输入序列分成两个长度为n/2的子序列；

1. 对这两个子序列分别采用归并排序；
1. 将两个排序好的子序列合并成一个最终的排序序列。

------------

##### 5.2 代码实现
    void meage(int arr[],int p,int mid,int r)//归并函数
    {
    	int left=p;//左侧队伍的头指针，指向待比较的元素 
    	int right=mid+1;//右侧队伍的头指针，指向待比较的元素 
    	int current=p;//原数组的指针，指向待填入的数据
		int help[n];//辅助空间，用来保存原始数据
    	for(int i=p;i<=r;i++)
    	{
    		help[i]=arr[i];
    	}
    	while(left<=mid&&right<=r)
    	{
    		if(help[left]<=help[right])
    		{
    			arr[current++]=help[left++];
    		}
    		else
    		{
    			arr[current++]=help[right++];
    		}
    	 }
    	 while(left<=mid)
    	{
    		arr[current++]=help[left++];
    	}
    }
    void Mergsort(int arr[],int p,int r)//归并排序
    {
    	if(p<r)
    	{
    		int mid=p+((r-p)>>1);
    		Mergsort(arr,p,mid);//左边排序
    		Mergsort(arr,mid+1,r);//右边排序
    		meage(arr,p,mid,r);//合并两边
    	} 
    }

##### 5. 3 算法分析

**最佳情况：T(n) = O(n)  最差情况：T(n) = O(nlogn)  平均情况：T(n) = O(nlogn)**

------------

未完待续

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

zdw

TA的其他文章

你可能喜欢

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

假币问题（C语言代码）

C语言训练-8除不尽的数（C语言代码）暴力解法，答案只有一个，直接输出就好了

C语言训练-阶乘和数* （C语言代码）

点我有惊喜！你懂得！

排序算法总结之-冒泡、选择、插入、希尔、归并排序（含C++代码实现）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

川哥的吩咐（C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(3) （C语言代码）

简单的a+b （C语言代码）

WU-格式化数据输出（C++代码）

三角形（C++代码）递推

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

C语言程序设计教程（第三版）课后习题6.8 （C语言代码）

【计算直线的交点数】（C语言代码）

zdw

TA的其他文章

你可能喜欢

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

假币问题 （C语言代码）

C语言训练-8除不尽的数 （C语言代码）暴力解法，答案只有一个，直接输出就好了

C语言训练-阶乘和数* （C语言代码）

点我有惊喜！你懂得！

排序算法总结之-冒泡、选择、插入、希尔、归并排序（含C++代码实现）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

川哥的吩咐 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(3) （C语言代码）

简单的a+b （C语言代码）

WU-格式化数据输出 （C++代码）

三角形 （C++代码）递推

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

C语言程序设计教程（第三版）课后习题6.8 （C语言代码）

【计算直线的交点数】 （C语言代码）

假币问题（C语言代码）

C语言训练-8除不尽的数（C语言代码）暴力解法，答案只有一个，直接输出就好了

　　评论区

川哥的吩咐（C语言代码）

WU-格式化数据输出（C++代码）

三角形（C++代码）递推

【计算直线的交点数】（C语言代码）