猫头鹰的咖啡馆-数据结构与算法-如何理解那些“死记硬背”的排序

• 前言
• 一、冒泡排序
• 二、选择排序
• 三、打牌时的插入排序和希尔排序
• 四、快速排序
• 五、归并排序
• 六、堆排序
• • 1. 堆是什么
  • 2. 堆的特点
  • 3. [基本思想](https://blog.csdn.net/weixin_50886514/article/details/114847405)
• 总结

无论是校招还是社招，排序是绕不开的基础算法，甚至已经工作三年的我此时并不知道为何要面排序。冒泡，快速，归并，你未必理解，但像背古文一样背总是可以的。但后面我刷了一些二叉树和链表的题目，看到归并与快速在相关题目中的应用，大概有了一丝丝共鸣，排序终究是有用的。锻炼一种算法思维。
但具体什么应用此刻的我大概是说不出什么的。我想我会带着疑问上路，我也可以告诉我自己，就像很多年前我的数学老师告诉我的那样，你要理解着记忆。在生活中应用到它，才能真正的掌握它。
悉达多说，我会思考，我会斋戒，我会等待。

以下排序默认为从小到大排列。

一句话概括：从头到尾遍历元素，将当前元素和后面元素比较，选择往后最小的数与当前元素进行交换，这样第一趟便将最小的数放在第一个位子，以此类推。遍历N*N次后，完成排序。

算法实现

void BubbleSort(vector&nums, int n) {
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (nums[j] < nums[i]) {
                swap(nums[i], nums[j]);
            }
        }
    }
}

一句话概括：如上面的冒泡排序一样，选择排序从头到尾遍历元素，将当前元素和后面元素比较，不断更新最小元素的位置index，最后与当前元素进行交换。同样是遍历N*N次。与冒泡排序相比，选择排序不断更新最小数的index，最后才做一次交换。

算法实现
我有时候觉得人生就是一个不断选择的过程，只有非常知道自己要什么，心才能像是掉进湖水中，一直往下沉，一直在探索，寻找最终的目标。

void SelectSort(vector&nums, int n)
{
	for (int i = 0; i < n; i++) {
		int minIndex = i; // 这是很巧的一点, 使用了index而不是直接使用minNum. 方便后面的互换.
		for (int j = i + 1; j < n; j++) {
			if (nums[j] < nums[minIndex]) {
				minIndex = j;
			}
		}
		swap(nums[i], nums[minIndex]);
	}
}

一句话概括：插入排序就像是将一张牌插入前面已经排好的牌中。你会找到第一个小于当前牌的位置，然后将牌插到它的前面。这样，后面的牌都要向后移动一个，前面的牌保持不动。重复上述步骤。

算法实现
打牌发明出来的算法

void InsertSort(vector&nums, int n)
{
	for (int j = 1; j < n; j++) {
		int key = nums[j]; // 待排序的第一个元素
		int i = j - 1; // 表示已经排序的最后一个元素
		while(i >= 0 && key < nums[i]) {
			nums[i+1] = nums[i]; // 从后向前逐个比较key与已经排过序的数字的比较，如果比它小，当前字符向后移动一位
			i--;
		}
		nums[i+1] = key;
	}
}

一句话概括：希尔排序是对插入排序的改进，不同之处在于，插入排序比较的是当前值与之前的已排列完成元素的大小，而希尔排序会优先比较距离较远的元素，然后逐渐缩小gap，因此又称为缩小增量排序。
举个栗子：
1，先取一个小于len的整数d1(如len / 2)作为第一个增量，将数组分成d1组，每组len/d1的元素。
第一个组[1, 1 + d1, 1 + 2d1]
第二个组[2, 2 + d1, 2 + 2d1]
2，在各个组内部进行插入排序，因此每个组都变成了有序数组
3，取步长d2(如d1/2), 再将数组分成d2个组, 每个组len/d2个元素.因此每个的间隔都是d2[i, i + d2, i + 2d2]。在局部有序中排列，自然要比整体无序中的排列更快速一点。
4，重复上述步骤，一直到步长为1为止。

void ShellSort(vector &nums, int len)
{
	int i, j, gap;
	for (int gap = len / 2; gap > 0; gap /= 2) {
		// 一共有gap个组
		for (int i = 0; i < len; i++) {
			for (int j = i + gap; j < len; j += gap) {
				// 进行插入排序, j是当前值, 不断的插入之前的原有队列中
				if(nums[j] >= nums[i]) { // 说明是希望从大到小排列
					continue;
				}
				int tmp = nums[j];
				int k = j - gap;
				while(k >= 0 && nums[k] < tmp) {
					nums[k+gap] = nums[k];
					k-=gap;
				}
				nums[k + gap] = tmp;
			}
		}
	}
}

一句话概括：快速排序的思想是每趟排序时选出一个基准值，然后将所有元素与该基准值比较，并按大小分成左右两堆，然后递归执行该过程，直到所有元素都完成排序。

void quickSort(int left, int right, vector& arr)
{
	if(left >= right)
		return;
	int i, j, base, temp;
	i = left, j = right;
	base = arr[left];  //取最左边的数为基准数
	while (i < j)
	{
		while (arr[j] >= base && i < j)
			j--;
		while (arr[i] <= base && i < j)
			i++;
		if(i < j)
		{
			temp = arr[i];
			arr[i] = arr[j];
			arr[j] = temp;
		}
	}
	//基准数归位
	arr[left] = arr[i];
	arr[i] = base;
	quickSort(left, i - 1, arr);//递归左边
	quickSort(i + 1, right, arr);//递归右边
}

一句话概括：快速排序的思想是每趟排序时选出一个基准值，然后将所有元素与该基准值比较，并按大小分成左右两堆，然后递归执行该过程，直到所有元素都完成排序。
归并排序是分治法的一种应用，如果有机会，会单独讲一章分治法。包括表达式求值，汉诺塔和本题的归并排序。
分治法：将一个大的问题分成若干个子问题，对子问题直接答案的合并就成了一个大的问题，因此分治是建立在递归基础上的。
使用场景：
（1）分解：一个大问题可拆分成若干个相互独立且与大问题形式相同的小问题.（保证了你可以使用递归法）
（2）求解：子问题规模较小且可以直接被解决，使用递归法解决各个子问题.
（3）合并：将各个子问题的解合并为原问题的解.

第一步：建立新的数组，其大小为两个已经排序序列之和，用来存放合并后的序列。
第二步：设定两个index分别为两个已经排序序列的起始位置。firstIndex和secondIndex
第三步：比较两个index所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置。
重复步骤三，直到某一指针超出序列尾。
第四步：将另一序列剩下的所有元素直接复制到合并序列尾部

```cpp

// 治，也就是合并
void Merge(vector &numbers, int start, int mid, int end) {
    vector temp(end - start + 1, 0); //第一步，申请空间，大小为两个排序序列之和
    int fistSectionIndex = start;			//第二步，设定两个待排序列的起始位置的索引
    int secondSectionIndex = mid + 1;
    int tempIndex = 0;	//所申请空间的索引

    while (fistSectionIndex <= mid && secondSectionIndex <= end) {	//直到两个序列中有一个到达终止位置
        if (numbers[fistSectionIndex] <= numbers[secondSectionIndex])
            temp[tempIndex++] = numbers[fistSectionIndex++];
        else
            temp[tempIndex++] = numbers[secondSectionIndex++];
    }

    while (fistSectionIndex <= mid)
        temp[tempIndex++] = numbers[fistSectionIndex++];

    while (secondSectionIndex <= end)
        temp[tempIndex++] = numbers[secondSectionIndex++];

    for (int j = 0; j < tempIndex; ++j)		//将合并且排序好的元素，复制到原来的数组中，释放临时数组空间
        numbers[start + j] = temp[j];
}


void MergeSort(vector &numbers, int start, int end) {
    if (start >= end)
        return;

    int mid = (start + end) / 2;
	// 分
    MergeSort(numbers, start, mid);		//递归排序numbers[start,mid](首先从上往下递归分解到最底层元素个数为1的情况)
    MergeSort(numbers, mid + 1, end);	//递归排序numbers[mid + 1,end](首先从上往下递归分解到最底层元素个数为1的情况)

    Merge(numbers, start, mid, end);	//然后递归的从下往上合并排序
}

int main() {
    vector nums{ 5,6,1,8,3,4,9,7,2,3 };
    cout << "归并排序前：";
    for (int i = 0; i < 10; i++)
        cout << nums[i] << ' ';
    cout << endl;

    MergeSort(nums, 0, 9);

    cout << "归并排序后：";
    for (int i = 0; i < 10; i++)
        cout << nums[i] << ' ';
    cout << endl;
}

堆也是一种数据结构，完全二叉树。

大顶堆，父节点值大于子节点
小顶堆，父节点值小于子节点