【C++实现插入排序、希尔排序、冒泡排序、快速排序、选择排序】

使用C++实现来插入排序、希尔排序、冒泡排序、快速排序、选择排序算法。

一、插入排序

插入排序，一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法 。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而生成一个新的、记录数增1的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动 。

插入排序的工作方式像许多人排序一手扑克牌。开始时，我们的左手为空并且桌子上的牌面向下。然后，我们每次从桌子上拿走一张牌并将它插入左手中正确的位置。为了找到一张牌的正确位置，我们从右到左将它与已在手中的每张牌进行比较。拿在左手上的牌总是排序好的，原来这些牌是桌子上牌堆中顶部的牌 。

插入排序是指在待排序的元素中，假设前面n-1(其中n>=2)个数已经是排好顺序的，现将第n个数插到前面已经排好的序列中，然后找到合适自己的位置，使得插入第n个数的这个序列也是排好顺序的。按照此法对所有元素进行插入，直到整个序列排为有序的过程，称为插入排序 。

#include<iostream>
using namespace std;

int main()
{
	int arr[6]={9,7,6,5,4,3};
	//遍历数组，依次进行比较 
	for(int i=0;i<5;i++){
		/*
		比较i和i+1，如果升序排序，则判断第i个元素是否大于第i+1个
		元素，如果是，则将第i+1个元素依次与之前的所有元素进行比较并
		排序，完成后将第i个元素插入到第i+1个元素的位置上。降序也是
		同样的原理。 
		*/ 
		if(arr[i]>arr[i+1]){
			//交换
			//从第i个元素开始交换 
			int j=i;
			//将需要插入的元素使用变量temp保存 
			int temp=arr[i+1];
			/**
			将第i个元素之前的所有元素进行一次重新排序，保证第0-i个元素
			之间是排好序的。 
			*/ 
			while(j>=0&&temp<arr[j]){
				arr[j+1]=arr[j];
				j--;
			}
			arr[j+1]=temp;
		}
	}
	//打印输出排序结果 
	for(int i=0;i<6;i++){
		cout<<arr[i]<<" ";
	}
 } 

二、希尔排序

希尔排序(Shell’s Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因 D.L.Shell 于 1959 年提出而得名。

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

#include<iostream>
using namespace std;

int main()
{
	int arr[6]={9,7,6,5,4,3};
	//控制步长 
	for(int gap=6/2;gap>0;gap/=2){
		//遍历所有的组 
		for(int i=0;i<gap;i++){
			//遍历每个组中的所有元素 
			for(int j=i-gap;j>=0;j-=gap){
				/*
				比较第j个元素和第j+gap个元素，不满足排序规则的交换
				元素顺序。 
				*/ 
				if(arr[j]>arr[j+gap]){
					int t=arr[j];
					arr[j]=arr[j+gap];
					arr[j+gap]=t;
				}
			}
		}
	} 
	//打印输出排序结果 
	for(int i=0;i<6;i++){
		cout<<arr[i]<<" ";
	}
 } 

三、冒泡排序

冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。

它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行，直到没有相邻元素需要交换，也就是说该元素列已经排序完成。

这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

冒泡排序算法的原理如下：

比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

#include <iostream>
using namespace std;

int main()
{
    int array[8] = {8,7,6,5,4,3,2,1};
    //打印输出排序前的数组 
    cout<<"排序前的数组为：";
    for (int i = 0; i < 8; i++){
        cout<<array[i]<<" ";
    }
    //冒泡排序 
    for(int i=0;i<8;i++){
    	for(int j=0;j<8-1-i;j++){ 
    		if(array[j]>array[j+1]){
    			int temp=array[j];
    			array[j]=array[j+1];
    			array[j+1]=temp;
			}
		}
	}
    //打印输出排序后的数组 
    cout<<"\n排序后的数组为：";
    for (int i = 0; i < 8; i++){
        cout<<array[i]<<" ";
    }
    
    return 0;
}

 

海报图正在生成中...

竖版 宽版