选择排序，插入排序，快速排序

发表于

「这是我参与11月更文挑战的第18天，活动详情查看：2021最后一次更文挑战」

选择排序

选择排序（Select Sort） 是直观的排序，通过一个中间量从带排序的的数中找出最大或最小的交换到对应位置。再选择次之。选择排序和冒泡排序一样，都有两层循环。

让我们通过动态图来看一下选择排序的过程图：
在这里插入图片描述
让我们通过动态图来看一下选择排序的过程图：

这个动态图演示了一个无序数组使用选择排序转变为一个从大到小的有序数组，让我们来观察一下，在进入内循环之前，会记录一个值，这个值是当前外层循环A[i]的值，之后拿着这个值，在内循环遍历数组的时候，跟数组的元素一个一个的比较，如果这个值比当前下标的元素的大，那么就双方的值继续交换，内循环完成后，将这个值再赋值给A[i]，经过内循环怎么一折腾，最后A[i]一定是拿到最小或者最大的值。

和冒泡排序不一样的是冒泡排序如果两个不一样当场就交换，而选择排序是将值给了一个中间变量，让这个中间变量加入内循环，等内循环结束，把真正最大或者最小的值赋值给外出循环的A[i]。

选择排序原理总结

[1]记录数组第一个元素的值（数组长度n）。

[2]遍历n-1次，用该值与其他元素比较，找到最大或者最小的一个数交换。

[3]记录数组第二个元素的值。

[4]遍历n-2次，用该值与其他元素比较，找到最大或者最小的一个数交换。

[5]重复上述步骤，遍历N次，直到没有要比较的数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
cpp复制代码  int array[] = { 7,10,12,3,9,5 };
  for (int i = 0; i < 6; i++)
  {
    int minkey = i;
    for (int j = i + 1; j < 6; j++)
    {
      if (array[minkey] > array[j])
      {
      	minkey = j;
      }
    }
      int tamp = array[i];
      array[i] = array[minkey];
      array[minkey] = tamp;
  }

插入排序

百度百科上面有一个不错的例子是这样描述插入排序的，插入排序的工作方式像许多人排序一手扑克牌。开始时，我们的左手为空并且桌子上的牌面向下。然后，我们每次从桌子上拿走一张牌并将它插入左手中正确的位置。为了找到一张牌的正确位置，我们从右到左将它与已在手中的每张牌进行比较。这样，拿在左手上的牌总是排序好的。

用一个动态图演示插入排序过程：
在这里插入图片描述
首先把数组第一个元素a[0]看作是一个有序数列，然后a[1]开始与a[0]做比较，发现10比7大，那么a[1]的值需要插入在a[0]的前面，表示下来就是a[0]的值往后移到a[1]，然后a[1]的值移向a[0]，然后再拿a[2]与之前的有序数列a[0]，a[1]做比较，发现12大于10和7，那么原来的a[0]的值和a[1]的值，继续向右移动一个单位，把a[2]的值插入a[0]，如此，a[0]，a[1]，a[2]就是一个有序数列，如此往复，直到之后排序完成。

插入排序原理

1、将待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列；

2、取出下一个元素，在已经排序的元素序列中从后向前扫描；

3、如果该元素（已排序）大于新元素，将该元素移到下一位置；

4、重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；

5、将新元素插入到该位置后；

6、重复步骤2~5。

代码

1
2
3
4
5
6
7
8
9
10
11
cpp复制代码	int arr[] = { 1,5,69,8,10 };
	int j;
	for (int i = 1; i < 5; i++)
	{
		int temp = arr[i];
		for (j = i - 1;j >= 0 && arr[j] < temp;j--)
		{
			arr[j + 1] = arr[j];
		}
		 arr[j+1]= temp;
	}

快速排序

快速排序是对冒泡排序的一种改进。它的基本思想是：通过一次排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一不部分的所有数据都要小，然后再按次方法对这两部分数据分别进行快速排序，整个排序过程可以递归或者非递归进行，以此达到整个数据变成有序序列。

快速排序过程图：
hgfh
快速排序和归并排序有一些相同点和一些不同点，比如两种都使用了分治的思想，都是递归+排序，不同点在于归并排序是先递归后排序，而快速排序是先排序，后递归。

快速排序原理

1）设置两个变量i、j，排序开始的时候：i=0，j=N-1； [1]
2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]； [1]
3）从j开始向前搜索，即由后开始向前搜索(j–)，找到第一个小于key的值A[j]，将A[j]和A[i]的值交换； [1]
4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]的值交换； [1]
5）重复第3、4步，直到 i 等于 j； (3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外， i 等于 j 这一过程一定正好是i+或j-完成的时候，此时令循环结束）。

代码

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
cpp复制代码void func(int * a, int s, int e)
{
	//快速排序使用的是分治法，我们可以使用递归来重复操作

	if (s == e)return;
	//排序
	int i = s;
	int j = e;
	int data = a[s];
	int arrint = s;
	while (j != i)
	{
		//从右往左遍历
		for (int f = j; f >=s; f--)
		{
			if (j == i)	break;
			if (data <= a[f])
			{		
				int temp = a[f];
				a[f] = a[arrint];
				a[arrint] = temp;
				arrint = f;
				j = f - 1;
				break;
			}
			j = f - 1;
		}
		//从左往右遍历
		for (int f = i; f <= e; f++)
		{
			if (j == i)	break;
			if (data >= a[f])
			{
				int temp = a[f];
				a[f] = a[arrint];
				a[arrint] = temp;
				arrint = f;
				i = f+1;
				break;
			}
			i = f + 1;
		}
	}
	int min = s + (e - s) / 2;
	func(a, s, min);
	func(a, min + 1, e);
}

int main()
{
	//归并的参数值 和快速参数值的不同作用
	int a[] = { 8,7,10,12,4,5,6,9 };
	func(a, 0, 7);

	for (int i = 0; i <8; i++)
	{
		cout << a[i] << " ";
	}
	return 0;
}

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%