面试基础题【2】--排序算法

----接上

面试基础题【1】--排序算法_追求决定高度的博客-CSDN博客

1.4 ----shellSort

排序算法        平均时间复杂度        最好情况        最坏情况        空间复杂度        稳定性

希尔排序        O(nlogn)                 O(nlog^2 n)      O(nlog^2 n)        O(1)               不稳定

 排序思路：基于简单的插入排序的改进，也叫缩小增量排序。

简单插入排序问题：当插入的数较小，左有序表元素与插入的值比较的次数增多以及左表元素后移的次数增多，效率较低。

void shellSort(vector<int>& nums) {
	for (int gap = nums.size() / 2; gap > 0; gap /= 2){//分组递减
		
        //增量为gap 的两个数进行对比  例如：nums[0]--nums[gap] 
        //令最大下标的数下标为 gap，保证 每一个都能比较完    
        for (int i = gap; i < nums.size(); i++){
			for (int j = i - gap; j >= 0; j -= gap) {
				if (nums[j] > nums[j+gap]) {
					int t = nums[j];
					nums[j] = nums[j+gap];
					nums[j+gap] = t;
				}
			}
		}
	}
	return nums;
}

1.5 ----mergeSort

排序算法        平均时间复杂度        最好情况        最坏情况        空间复杂度        稳定性

归并排序        O(nlogn)                 O(nlog n)      O(nlog n)        O(n)                      稳定

排序思想：采用分治法的思想，将大问题划分为小问题进行递归求解-分而治之

 

代码：

void merge(vector<int>& nums, int left, int mid, int right) {
	int i = left; int j = mid+1; int t = 0;
	vector<int>temp(nums.size(),0);
	while (i <= mid && j <= right)
	{
		if (nums[i] <= nums[j])temp[t++] = nums[i++];
		else temp[t++] = nums[j++];
	}
	while (i <= mid)temp[t++] = nums[i++];//左边序列剩元素
	while(j<=right)temp[t++] = nums[j++];//右边剩元素
	
	for (int i = 0; i < right-left+1; i++) { //小区间合并->大区间合并
		nums[i + left] = temp[i];
	}
}
void mergeSort(vector<int>& nums,int left,int right) {
	//拆到一个区间只有一个元素时结束
    if (left < right) {
		int mid = (left + right) / 2;
		mergeSort(nums, left, mid);//左边区间一直拆
		mergeSort(nums, mid + 1, right);//右边区间一直拆
 
		merge(nums, left, mid, right);
        //拆完开始一个一个合并
        //先比较并合并左边/右边    
	}
}

1.5 ----quickSort

排序算法        平均时间复杂度        最好情况        最坏情况        空间复杂度        稳定性

快速排序        O(nlogn)                 O(nlog n)           O(n^2)          O(logn)               不稳定

排序思想：分治法+填坑【递归思想】

与“归并”不同的是，快排的分区是按照基准值进行分区的，将比基准值小的分在左边， 比基准值大的分在右边。

代码：

void quickSort(vector<int>& nums, int left, int right) {
	int start = left; int end = right;
	if (start >= right)return;//递归结束条件
 
	int baseValue = nums[start];//设定一个基准值，用baseValue接收，防止start元素被替换
	while (start != end){//只要起始与终点不同 就执行
		while (nums[end] >= baseValue && end > start) {//比较终值与基准值的大小，如果大，就--，起始下标指向 end
			end--;
		}
		if (nums[end] < baseValue)swap(nums[start], nums[end]);//如果小，就交换
		while (nums[start] <= baseValue && end > start) {//此时指针指向了start，比较start开始的值与基准值的大小，如果小就++
			start++;
		}
		if (nums[start] > baseValue)swap(nums[start], nums[end]);//如果大，就交换，指针再次回到end
	}
//第一轮比较结束，此时基准值的位置为 start=end；
	quickSort(nums, left , start-1);//基准值的右侧区间进行比较
	quickSort(nums, start+1 , right);//基准值的左侧区间进行比较
}