经典排序总结

港控/mmm° 2022-02-03 03:41 184阅读 0赞

**冒泡排序**（稳定）  
依次比较两个相邻的元素，把大的换到后面，一次循环完成后的结果是，最大的数字排在最后。重复以上步骤（除了最后一个），直到排完。

*  平均时间复杂度：O（n^2）
 *  最优时间复杂度：O（n）

void bubble_sort(vector<int>&nums)
    { 
    	int len=nums.size();
    	for(int i=0;i<len;i++)
    	{ 
    		for(int j=0;j<len-i-1;j++)
    		{ 
    			if(nums[j]>nums[j+1])swap(nums[j],nums[j+1]);
    		}
    	}
    }

**选择排序**

*  简单选择排序（不稳定）  
    选择序列中数最小的，把她插到第一个位置，依次类推。
 *  n个数需要进行比较的次数是n(n-1)/2
 *  时间复杂度为O（n^2）
 *  进行移动操作的时间复杂度为O（n）

void select_sort(vector<int>&nums)
    { 
    	int len=nums.size();
    	for(int i=0;i<len;i++)
    	{ 
    		int temp=i;
    		for(int j=i;j<len;j++)
    		{ 
    		if(nums[temp]>nums[j])temp=j;
    		}
    		swap(nums[i],nums[temp]);
    	}
    }

*  堆排序

**插入排序**

*  直接插入排序（稳定）  
    把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录都插完。
 *  平均时间复杂度O（n^2)
 *  空间复杂度O（1）

void insert_sort(vector<int>&nums)
    { 
    	int len=nusms.size();
    	for(int i=1;i<len;i++)
    	{ 
    		int temp=nums[i];
    		int j=i;
    		while(j>=1&&temp<nums[j-1])
    		{ 
    			nums[j]=nums[j-1];
    			j--;
    		}
    		nums[j]=temp;
    	}
    }

*  折半插入排序  
    直接插入排序中要把插入元素与已有有序序列元素一次进行比较，效率非常低。  
    折半插入，使用折半查找的方式寻找插入点的位置，这样可以减少比较的次数，但移动的次数不变，时间复杂度和空间复杂度和直接插入排序一样，在元素较多的情况下能提高查找性能。

void insert_sort(vector<int>&nums)
    { 
    	int len=nums.size（）；
    	for(int i=1;i<len;i++)
    	{ 
    		int temp=nums[i];
    		int pre=0;
    		int end=i-1;
    		int mid;
    		while(pre<=end)
    		{ 
    			mid=(pre+end)/2;
    			if(nums[mid]>temp)end=mid-1;
    			else if(nums[mid]<=temp)pre=mid+1;
    		}
    		for(int j=i;j>=pre+1;j--)
                nums[j]=nums[j-1];
                nums[pre]=temp;
    	}
    }

**快速排序**  
Partition方法

public static int partition(int[] array, int lo,int hi){ 
    	int key=array[lo];
    	int i=lo;
    	int j=hi;
    	while(i<j){ 
    		while(array[j]>=key&&i<j)j--;
    		while(array[i]<=key&&i<j)i++;
    		swap(array,i,j);
    }
    	swap(array,lo,j);
    	return j;
    }

利用swap（）函数，必须要将大于key写在前面，小于key写在后面，这样才能够保证，当退出里卖弄第一while循环的是，当前的j一定指向小于key值的数，这样最后才能将该值与key值交换。

**希尔排序**  
即缩小增量排序，把所有的数按照一定的增量分组插入排序，减小增量重复上述动作，直到增量为1结束。

*  插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。
 *  但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。

void ShellSort(int array[])
    { 
    	int i,j;
    	int temp;//定义的临时变量
    for(int step=length/2;step>0;step/=2)//step是步长，并让之在循环中每次减小一半
    { 
    	for（i=step;i<LENGTH;i++）
    	{ 
    		temp=array[i];//保存每次遍历的元素，为之后的插入排序做准备
    		for(j=i-step;(j>=0&&array[j]>temp);j-=step)//遍历结束条件就是下标《0或者不满足规则（升序，降序）
    		{ 
    			array[j+step]=array[j];
    		}
    		array[j+step]=temp;//最后将这个临时变量放在对应位置
    	}
    }
    }

**归并排序**  
归并排序，是创建在归并操作上的一种有效的排序算法该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。  
1.迭代实现：

实现原理：

①申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列

②设定两个指针，最初位置分别为两个已经排序序列的起始位置

③比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置

④重复步骤③直到某一指针到达序列尾

⑤将另一序列剩下的所有元素直接复制到合并序列尾

void merge_sort(vector<int>&nums)
        { 
            int len=nums.size();
            int result[len];
            int i;
            for(int blocks=1;blocks<len;blocks*=2)
            { 
                i=0;
            for(int start=0;start<len;start+=2*blocks)
            { 
                int start1=start;
                int end1=(start+blocks)>len?len:start+blocks;
                int start2=end1;
                int end2=(start2+blocks)>len?len:start2+blocks;
                while(start1<end1&&start2<end2)
                { 
                    if(nums[start1]<nums[start2])
                    { 
                        result[i++]=nums[start1];
                        start1++;
                    }
                     else if(nums[start1]>=nums[start2])
                    { 
                        result[i++]=nums[start2];
                        start2++;
                    }
                }
                while(start1<end1)
                { 
                    result[i++]=nums[start1++];
                }
                while(start2<end2)
                { 
                    result[i++]=nums[start2++];
                }
                
                    
            }
                for(int i=0;i<len;i++)
                nums[i]=result[i];
            }
               
            
        }

2.递归实现

假设序列共有n个元素

①将序列每相邻两个数字进行归并操作，形成floor(n/2)个序列，排序后每个序列包含两个元素。

②将上述序列再次归并，形成floor(n/4)个序列，每个序列包含四个元素

③重复步骤②，直到所有元素排序完毕  
代码：

void merge_sort(vector<int>&nums,int*result,int start,int end)
        { 
            if(start>=end)return;
            int len=end-start;
            int start1=start;
            int end1=start+len/2;
            int start2=end1+1;;
            int end2=end;
            merge_sort(nums,result,start1,end1);
            merge_sort(nums,result,start2,end2);
            int i=start;
            while(start1<end1+1&&start2<end2+1)
                { 
                    if(nums[start1]<=nums[start2])
                    { 
                        result[i++]=nums[start1];
                        start1++;
                    }
                     else if(nums[start1]>nums[start2])
                    { 
                        result[i++]=nums[start2];
                        start2++;
                    }
                }
                while(start1<end1+1)
                { 
                    result[i++]=nums[start1++];
                }
                while(start2<end2+1)
                { 
                    result[i++]=nums[start2++];
                }
                for(int i=start;i<=end;i++)
                nums[i]=result[i];
                
            
        }

参考文献：  
1 [https://blog.csdn.net/marcosyw/article/details/72794216][https_blog.csdn.net_marcosyw_article_details_72794216]  
2 [https://blog.csdn.net/hlang8160/article/details/78940780][https_blog.csdn.net_hlang8160_article_details_78940780]  
3 [https://www.cnblogs.com/bulingpan/p/6416351.html][https_www.cnblogs.com_bulingpan_p_6416351.html]

[https_blog.csdn.net_marcosyw_article_details_72794216]: https://blog.csdn.net/marcosyw/article/details/72794216
[https_blog.csdn.net_hlang8160_article_details_78940780]: https://blog.csdn.net/hlang8160/article/details/78940780
[https_www.cnblogs.com_bulingpan_p_6416351.html]: https://www.cnblogs.com/bulingpan/p/6416351.html