七大排序

1.选择排序

1. 1基本思想

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
选择排序的思想其实和冒泡排序有点类似，都是在一次排序后把最小的元素放到最前面，或者将最大值放在最后面。但是过程不同，冒泡排序是通过相邻的比较和交换。而选择排序是通过对整体的选择，每一趟从前往后查找出无序区最小值，将最小值交换至无序区最前面的位置。

1.2 实现逻辑

① 第一轮从下标为 1 到下标为 n-1 的元素中选取最小值，若小于第一个数，则交换
② 第二轮从下标为 2 到下标为 n-1 的元素中选取最小值，若小于第二个数，则交换
③ 依次类推下去……

1.3 动图演示

绿色是当前最小值

1.4 全部代码

void SelectionSort(int* arr, int length)
{
    for (int i = 0; i < length; i++)
    {
        int min = i;
        int j = i;
        for (j; j < length; j++)
        {
            if (arr[j] < arr[min])
            {
                min = j;
            }
        }
        swap(arr[i], arr[min]);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2.冒泡排序

1. 1基本思想

冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。
作为最简单的排序算法之一，冒泡排序给我的感觉就像 Abandon 在单词书里出现的感觉一样，每次都在第一页第一位，所以最熟悉。冒泡排序还有一种优化算法，就是立一个 flag，当在一趟序列遍历中元素没有发生交换，则证明该序列已经有序。但这种改进对于提升性能来
说并没有什么太大作用。

1.2 实现逻辑

比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

1.3 动图演示

• 顺序的时候最快
• 反序的时候最慢

1.4 全部代码

#include
void BubbleSort(int* nums, int N)
{
	for (int i = 1; i < N; i++)
	{
		int isSort = 0;
		for (int j = 0; j < N - i; j++)
		{
			if (nums[j] > nums[j + 1])
			{
				isSort = 1;
				int temp = nums[j];
				nums[j] = nums[j + 1];
				nums[j + 1] = temp;
			}
		}
		if (isSort == 0)
		{
			return;
		}
	}
}
int main()
{
	int arr[] = { 5,8,1,2,3,7,4 };
	BubbleSort(arr, 7);
	for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
	{
		printf("%d ", arr[i]);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

3.快速排序

1. 1基本思想

1．先从数列中取出一个数作为基准数，记为x。
2．分区过程，将不小于x的数全放到它的右边，不大于x的数全放到它的左边。（这样key的位置左边的没有大于key的，右边的没有小于key的，只需对左右区间排序即可）
3．再对左右区间重复第二步，直到各区间只有一个数

1.2 实现逻辑

定义一个key用来比较（key一般取数组第一个数)
R先走，先从右边找比key小的，遇到小的就停下来
L等R走完再走，L从左边找比key大的。

1.3 动图演示

1.4 全部代码

void QuickSort(int* arr, int L, int R) //挖坑法
{
	if (L >= R)
	{
		return;
	}
	int left = L;
	int right = R;
	int first = arr[left];
	while (left < right)
	{
		while (left < right && arr[right] >= first)
		{
			right--;
		}

		if (left < right)
		{
			arr[left] = arr[right];
		}

		while (left < right && arr[left] <= first)
		{
			left++;
		}

		if (left < right)
		{
			arr[right] = arr[left];
		}

		if (left == right)
		{
			arr[left] = first;
		}
	}
	QuickSort(arr, L, left - 1);
	QuickSort(arr, left + 1, R);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

4.希尔排序

1. 1基本思想

希尔排序是将待排序的数组元素 按下标的一定增量分组 ，分成多个子序列，然后对各个子序列进行直接插入排序算法排序；然后依次缩减增量再进行排序，直到增量为1时，进行最后一次直接插入排序，排序结束。

1.2 实现逻辑

选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
按增量序列个数 k，对序列进行 k 趟排序；
每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

1.3 图片展示

1.4 全部代码

void ShellSort(int* arr, int length)
{
	int gap = length;
	while (gap > 1)
	{
		gap /= 2;
		for (int i=0; i < length - gap; i++)
		{
			int end = i;
			int temp = arr[end + gap];
			while (end >= 0)
			{
				if (temp < arr[end])
				{
					arr[end+gap] = arr[i];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			arr[end+gap] = temp;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

5.插入排序

1. 1基本思想

每一步将一个待排序的数据插入到前面已经排好序的有序序列中，直到插完所有元素为止。

1.2 实现逻辑

将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

1.3 动图演示

1.3 动图演示

1.4 全部代码

void InsertSort(int* arr, int length)
{
	for (int i = 0; i < length-1; i++)
	{
		int end = i;
		int temp = arr[end + 1];
		while (end >= 0)
		{
			if (temp < arr[end])
			{
				arr[end + 1] = arr[end];
				end--;
			}
			else
			{
				break;
			}
		}
		arr[end + 1] = temp;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

6.堆排序

1. 1 什么是堆

堆是一种非线性结构，（本篇随笔主要分析堆的数组实现）可以把堆看作一个数组，也可以被看作一个完全二叉树，通俗来讲堆其实就是利用完全二叉树的结构来维护的一维数组
按照堆的特点可以把堆分为大顶堆和小顶堆
大顶堆：每个结点的值都大于或等于其左右孩子结点的值
小顶堆：每个结点的值都小于或等于其左右孩子结点的值
（堆的这种特性非常的有用，堆常常被当做优先队列使用，因为可以快速的访问到“最重要”的元素）

1.2 基本思想

将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值，
如此反复执行，便能得到一个有序序列了，建立最大堆时是从最后一个非叶子节点开始从下往上调整的（这句话可能不好太理解），下面会举一个例子来理解堆排序的基本思想

1.2 实现逻辑

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：

1. 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
2. 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；

堆排序的平均时间复杂度为 Ο(nlogn)。

1.3 动图演示

1.4 全部代码

void AdjustDown(int* a, int length, int parent) //现在是建大堆
{
	int child = parent * 2 + 1;
	while (child < length)
	{
		if (child + 1 < length && a[child] < a[child + 1])
		{
			child++;
		}
		if (a[parent] < a[child])
		{
			Swap(&a[parent], &a[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void HeapSort(int* arr, int length) //升序建大堆，降序建小堆
{
	assert(arr);
	for (int i = (length - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(arr, length, i);
	}
	
	int end = length - 1;
	while (end)
	{
		Swap(&arr[0],&arr[end]);
		AdjustDown(arr, end, 0);
		end--;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

7.归并排序

1. 1基本思想

归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：

• 自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）；
• 自下而上的迭代；

1.2 实现逻辑

1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
4. 重复步骤 3 直到某一指针达到序列尾；
5. 将另一序列剩下的所有元素直接复制到合并序列尾。

1.3 动图演示

1.4 全部代码

void MergeSort(int* arr, int * temp,int L, int R)
{
	if (L >= R)
	{
		return;
	}
	int mid = (L + R) / 2;
	MergeSort(arr,temp,L, mid);
	MergeSort(arr,temp, mid + 1, R);
	int left = L, right = mid + 1,k = L;
	while (left <= mid && right <= R)
	{
		if (arr[left] < arr[right])
		{
			temp[k++] = arr[left++];
		}
		else
		{
			temp[k++] = arr[right++];
		}
	}
	while (left != mid + 1)
	{
		temp[k++] = arr[left++];
	}
	while (right != R + 1)
	{
		temp[k++] = arr[right++];
	}
	for(int i=L;i<=R;i++)
	{
		arr[i] = temp[i];
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34