排序算法-白红宇

排序算法

阅读量：2427 次

发布时间：2019-05-10

本文共 4406 字，大约阅读时间需要 14 分钟。

冒泡算法

冒泡算法的基本思想是：

比较相邻的元素，如果第一个比第二个大，就交换他们两个

对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这一步做完后，最后的元素会是最大的数

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

在这里插入图片描述

冒泡排序代码：

class Solution {public:	vector
   
     bubblingSort(vector
    
      nums) {		for (int i = 0; i < nums.size() - 1; i++) {			for (int j = 0; j < nums.size() - 1; j++) {				if (nums[j] > nums[j + 1]) {					int temp = nums[j];					nums[j] = nums[j + 1];					nums[j + 1] = temp;				}			}		}		return nums;	}};

在效率上,在数据量比较大的时候,冒泡排序效率最低.所以,在数据规模比较小的情况下,可以考虑使用冒泡排序

优化冒泡排序

在普通冒泡排序的基础上，若我们发现一趟排序中没有发生任何交换，则说明数组排序已经完成

相关代码如下：

class Solution {public:	vector
   
     bubblingSort(vector
    
      nums) {		for (int i = 0; i < nums.size() - 1; i++) {			bool Sort=flase;			for (int j = 0; j < nums.size() - 1; j++) {				if (nums[j] > nums[j + 1]) {					int temp = nums[j];					nums[j] = nums[j + 1];					nums[j + 1] = temp;					Sort=true;				}			}			if(!Sort)break;		}		return nums;	}};

选择排序

选择排序是最稳定的排序算法之一，因为无论什么数据进去都是O(n²)的时间复杂度

选择排序的思想是：首先整个序列分为两个部分：已排序和未排序，每次都在未排序序列中找到最大/最小元素，存放到排序序列的起始位置。然后，再从剩余未排序元素中继续寻找到最大/最小元素，依次类推，直至所有元素均排序完毕

n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果：

初始状态：无序区R[1……n]，有序区为空

第i趟排序开始时，当前有序区和无序区分别为R[1……i-1]和R[i……n)，该趟排序从当前无序区中选出关键字最小的记录R[k]，将它与无序区的第一个记录交换，使R[1……i]和R[i+1……n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区

n-1趟结束，数组有序化了

相关代码如下：

#include
   
    #include
    
     using namespace std;class Solution {public:	vector
     
       selecttionSort(vector
      
        nums) {		for (int i = 0; i < nums.size()-1; i++) {			int minIndex = i;//记录无序区首元素位置			for (int j = i; j < nums.size() - 1; j++) {  //每次都从无序区中寻找最小的元素				if (nums[j] < nums[minIndex])minIndex = j;			}			//无序区中最小的元素与无序区第一个元素交换			int temp = nums[i];			nums[i] = nums[minIndex];			nums[minIndex] = temp;		}		return nums;	}};

插入排序

插入排序的基本思想是：在待排序的元素中，假设前面n-1个数已经是排好顺序的，现将第n个数据插到前面已经排好的序列中，然后找到合适自己的位置，使得插入第n个数的这个序列也是排好顺序的，按照此法对所有元素进行插入，知道整个序列排为有序的过程

相关代码如下：

#include
   
    #include
    
     using namespace std;class Solution {public:	vector
     
       insertSort(vector
      
        nums) {		for (int i = 1; i < nums.size(); i++) {			int temp = nums[i];			int j = i-1;			while (j >= 0 && nums[j] > temp) {				nums[j + 1] = nums[j];				j--;			}			nums[j + 1] = temp;		}		return nums;	}};

希尔排序

希尔排序也是一种插入排序，它是简单插入排序经过改进之后一个更加高效的版本，也称为缩小增量排序，希尔排序是非稳定排序算法，希尔排序的时间复杂度依赖于所选的步长

希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素一次性的朝最终位置前进一大步，然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序

#include
   
    #include
    
     using namespace std;class Solution {public:	vector
     
       insertSort(vector
      
        nums) {		for (int i = 1; i < nums.size(); i++) {			int temp = nums[i];			int j = i-1;			while (j >= 0 && nums[j] > temp) {				nums[j + 1] = nums[j];				j--;			}			nums[j + 1] = temp;		}		return nums;	}};

归并排序

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

把长度为n的输入序列分成两个长度为n/2的子序列

对这两个子序列分别采用归并排序

将两个排序好的子序列合并成一个最终的排序序列

相关代码如下：

#include
   
    #include
    
     using namespace std;class Solution {public:	void mergeSort(vector
     
      & nums,int left,int right) {		if (left >= right)return;		int mid = (left + right) / 2;		mergeSort(nums, left, mid);//对左边递归		mergeSort(nums, mid + 1, right);//对右半边递归		merge(nums, left, mid,right);//合并	}	//合并操作	void merge(vector
      
       & nums, int left, int mid, int right) {		int i = left, j = mid + 1, k = 0;		vector
       
         temp(right - left + 1);		while (left <= mid && j <= right) {			if (nums[i] < nums[j]) {				temp[k++] = nums[i++];			}			else {				temp[k++] = nums[j++];			}			while (left <= mid) {  //如果左半区域还有剩余，则直接将剩余的元素复制到新数组				temp[k++] = nums[i++];			}			while (j <= right) {  //如果右半区域还有剩余，则直接将剩余元素复制到新数组				temp[k++] = nums[j++];			}			nums = temp;		}	}};