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

今天跟老师交流了一下，注重数据结构以及一些基础算法的学习，面试不会太难，但很重视基础。

恍然间吓出一身冷汗！树、各种链表、各种排序等等我都不是很熟！┭┮﹏┭┮

今儿就来个排序算法吧！！！

Part.1——十大排序算法

个人记忆口诀：冒泡选择插，希尔归并快，堆、桶、计数、基

1.1----bubbleSort

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

冒泡排序        O(n^2)                        O(n)                O(n^2)                O(1)                稳定

排序思想：检查序列中的相邻元素，如果逆序就交换，进行 n-1次循环检查。

例子：-3  5  1 -2  8  7  冒泡排序

void bubbleSort(vector<int>& v)
{
	for (int i = 0; i < v.size()-1; i++){
		for (int j = 0; j < v.size()-1; j++){
			int tmp = 0;
			if (v[j] > v[j+1]) {
				tmp = v[j];
				v[j] = v[j+1];
				v[j+1] = tmp;
			}
		}
	}
	return v;
}

第一层循环：遍历次数；第二层循环：两两交换相邻元素，如果不满足从小到大/从大到小排序条件的话。

稳定：如果序列存在前后元素相等，排序后，该前后顺序不变。

优化：某次循环中，没有发生交换，就直接跳出。

1.2----selectionSort

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

选择排序        O(n^2)                        O(n^2)                O(n^2)           O(1)            不稳定

排序思想：

第一次检查，将0----n区间的最小值与v[0]进行交换；

第二次检查，将1----n-1区间的最小值与v[1]进行交换...以此类推 

例子：-3  5  1 -2  8  7   选择排序

void selectionSort(vector<int>& v) {
	for (int i = 0; i < v.size() - 1;i++)
	{
		int minnum = INT_MAX;
		int index;
		for (int j = i; j < v.size() - 1; j++) {
			if (minnum > v[j]) {
				minnum = v[j]; index = j;
			}
		}
			int tmp;
			tmp = v[i];
			v[i] = v[index];
			v[index] = tmp;
	}
	return v;
}

第一层循环：循环次数以及交换数值；

第二层循环：用来找到区间内最小值，并记住最小值的下标。

不稳定：前后相等的元素经过选择排序，相对位置可能会发生改变。

1.3----insertSort

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

插入排序        O(n^2)                        O(n)                O(n^2)           O(1)                 稳定

排序思想：

将 n 个序列分成两组，一个为有序表，另一个无序表。开始时，有序表只有一个元素，通过不断选择无序表中的第一个元素加入到有序表中，插入至有序表中的适当位置，使之成为新的有序表。 

void insertSort(vector<int>& v)
{
	for (int i = 1; i < v.size(); i++) {
		int insertVal = v[i];//准备插入左索引表的数
		int leftindex = i - 1;//左索引表的最后一个数的下标
		while (leftindex >= 0 && insertVal < v[leftindex])
			//如果左索引表还有数可以比较  且    右索引表中准备插入的值小于当前左索引表的值，此时需要进行替换
		{
			v[leftindex + 1] = v[leftindex];//要比较的数与比较的数始终相邻
			leftindex--;
		}
		if (leftindex + 1 != i)v[leftindex + 1] = insertVal;//当前的 v[i]已经变了，不能用v[i]了
	}
	return v;
}

第一层循环：遍历右无序表的数；第二层循环：当前右索引表的数与每一个左索引表的数作比较。

稳定：不会改变相同的两个相邻元素的相对顺序。