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

布满荆棘的人生 2024-03-17 11:37 84阅读 0赞

**使用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）错误就把他们交换过来。走访元素的工作是重复地进行，直到没有相邻元素需要交换，也就是说该元素列已经排序完成。
> 
> 这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。
> 
> 冒泡排序算法的原理如下：
> 
> 1.  比较相邻的元素。如果第一个比第二个大，就交换他们两个。
> 2.  对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
> 3.  针对所有的元素重复以上的步骤，除了最后一个。
> 4.  持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

#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;
    }

## 四、快速排序 ##

> 快速排序算法通过多次比较和交换来实现排序，其排序流程如下：
> 
> (1)首先设定一个分界值，通过该分界值将数组分成左右两部分。
> 
> (2)将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于分界值，而右边部分中各元素都大于或等于分界值。
> 
> (3)然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
> 
> (4)重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。  
> 原理
> 
> 设要排序的数组是A\[0\]……A\[N-1\]，首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它左边，所有比它大的数都放到它右边，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。
> 
> 一趟快速排序的算法是：
> 
> 1）设置两个变量i、j，排序开始的时候：i=0，j=N-1；
> 
> 2）以第一个数组元素作为关键数据，赋值给**key**，即**key**=A\[0\]；
> 
> 3）从j开始向前搜索，即由后开始向前搜索(j–)，找到第一个小于**key**的值A\[j\]，将A\[j\]和A\[i\]的值交换；
> 
> 4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于**key**的A\[i\]，将A\[i\]和A\[j\]的值交换；
> 
> 5）重复第3、4步，直到ij； 3、4步中，没找到符合条件的值，即3中A\[j\]不小于**key**,4中A\[i\]不大于**key**的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，ij这一过程一定正好是i++或j–完成的时候，此时令循环结束。
> 
> 排序演示
> 
> 假设一开始序列\{xi\}是：5，3，7，6，4，1，0，2，9，10，8。
> 
> 此时，ref=5，i=1，j=11，从后往前找，第一个比5小的数是x8=2，因此序列为：2，3，7，6，4，1，0，5，9，10，8。
> 
> 此时i=1，j=8，从前往后找，第一个比5大的数是x3=7，因此序列为：2，3，5，6，4，1，0，7，9，10，8。
> 
> 此时，i=3，j=8，从第8位往前找，第一个比5小的数是x7=0，因此：2，3，0，6，4，1，5，7，9，10，8。
> 
> 此时，i=3，j=7，从第3位往后找，第一个比5大的数是x4=6，因此：2，3，0，5，4，1，6，7，9，10，8。
> 
> 此时，i=4，j=7，从第7位往前找，第一个比5小的数是x6=1，因此：2，3，0，1，4，5，6，7，9，10，8。
> 
> 此时，i=4，j=6，从第4位往后找，直到第6位才有比5大的数，这时，i=j=6，ref成为一条分界线，它之前的数都比它小，之后的数都比它大，对于前后两部分数，可以采用同样的方法来排序。

#include <iostream>
     
    using namespace std;
     
    void Qsort(int arr[], int low, int high){
        
        if (high <= low){
        
        	return;
    	}
    	
        int left = low;
        int right = high;
        int key = arr[low];
        
        while (true)
        {
        
            //将比key小的值放key左边，比key大的值放key右边 
    		/*从左向右找比key大的值*/
            while (arr[left] <= key)
            {
        
                left++;//从左往右，下标递增 
                //当遍历到最后一个元素时，结束循环 
                if (left == high){
        
                    break;
                }
            }
            /*从右向左找比key小的值*/
            while (arr[right] >= key)
            {
        
                right--; //从右往左，下标递减 
                //当遍历到第一个元素时，结束循环 
    			if (right == low){
        
                    break;
                }
            }
    //        cout<<"left:"<<left<<" right:"<<right<<"\n"; 
            /*
    		当比key小的数全在左边，比key大的数全在右边时，表
    		示第一次排序完成，结束循环
    		*/ 
    		if (left >= right){
        
            	break;
    		}
            /*
    		将比key小的数移到左边，比key大的数移到右边，
    		交换left,right对应的值
    		*/
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
        }
        /*分别对左右两边的数字进行排序，
    	中枢值与right对应值交换*/
        arr[low] = arr[right];
        arr[right] = key;
        Qsort(arr, low, right - 1);
        Qsort(arr, right + 1, high);
    }
     
    int main()
    {
        
        int arr[] = {
        52, 64, 59, 52, 75, 28, 98, 30, 25};
        //获取数组长度 
    	int len = sizeof(arr)/sizeof(arr[0]); 
    	//打印排序前的数组
    	cout<<"排序前："; 
        for(int i = 0; i < len; i++)
        {
        
            cout << arr[i] << " ";
        }
        //调用快速排序函数 
    	Qsort(arr, 0, len- 1);
    	//打印排序后的数组 
        cout<<"\n排序后：";
        for(int i = 0; i < len; i++)
        {
        
            cout << arr[i] << " ";
        }
        return 0;
    }

## 五、选择排序 ##

> 选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。
> 
> **排序思路**：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
> 
> **具体实现方法**：
> 
> ①初始状态：无序区为R\[0…n-1\]（共n个元素），有序区为空。
> 
> ②第1趟排序
> 
> 设置一个变量i，让i从0至n-2循环的同时，在对比数组中元素i跟元素i+1的大小，如果R\[i+1\]比R\[i\]小，则用一个变量k来记住他的位置（即k=i+1）。等到循环结束的时候，我们应该找到了R中最小的那个数的位置了。然后进行判断，如果这个最小元素的不是R的第一个元素，就让第一个元素跟他交换一下值，使R\[0…0\]和R\[1…n-1\]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
> 
> ……
> 
> ③第i趟排序
> 
> 第i趟排序开始时，当前有序区和无序区分别为R\[0…i-1\]和R\[i…n-1\]。该趟排序从当前无序区中选出关键字最小的记录 R\[k\]，将它与无序区的第1个记录R交换，使R\[0…i\]和R分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
> 
> 图1例子：（通过寻找最小值的选择排序）
> 
> [![图1 选择排序（最小值）实例][1]][1 _1]

#include<iostream>
    
    using namespace std;
    
    /*遍历寻找当前序列中的最小值，返回最小值的下标*/
    int selectMin(int arr[],int i,int len){
        
    	int min=i;
    	for(;i<len;i++){
        
    		if(arr[i]<arr[min]){
        
    			min=i;
    		}
    	}
    	return min;
    }
    
    int main()
    {
        
    	int arr[]={
        5,8,2,4,1,6};
    	int len=sizeof(arr)/sizeof(arr[0]);
    	for(int i=0;i<len;i++){
        
            //接收当前序列的最小值下标
    		int j=selectMin(arr,i,len);
    		//判断最小值是否为当前元素，如果不是，则交换最小值和当前元素的位置
            if(i!=j){
        
    			int temp=arr[i];
    			arr[i]=arr[j];
    			arr[j]=temp;
    		}
    	}
    	for(int i=0;i<len;i++){
        
    		cout<<arr[i]<<" ";
    	}
      }

[1]: https://img-blog.csdnimg.cn/img_convert/70cf326358121550de3eb4b28f673949.png
[1 _1]: https://baike.baidu.com/pic/%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F/9762418/0/5bafa40f4bfbfbedab646a7c09b9e036afc37931b1d5?fr=lemma&fromModule=lemma_content-image&ct=single