（九）内部排序

冒泡排序

算法思想：
　　若数据个数为n,一次循环n-1次，每次比较相邻两个数据，以升序排列为例，若前者比后者
大，则交换两数据，即可得依次循环排序后的最大值放在最后面，之后循环n-2次…依次类推直
至排序完成。

代码：

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
#define MAXSIZE 20
typedef int Status;
typedef int ElemType;
typedef int KeyType;
typedef struct{
　　　KeyType key;	//关键字项
　　　//InfoType otherinfo; //其他数据项
}RedType;		//记录类型

typedef struct{
　　　RedType r[MAXSIZE+1];// r[0]闲置或用作哨兵单元
　　　int length; //顺序表长度
}SqList;	//顺序表类型

　Status BubbleSort(SqList &L){
　　　//冒泡排序
　　　　for(int i=L.length;i>=1;--i){
　　　　　　bool change=false;
　　　　　　for(int j=1;j<i;++j)
　　　　　　　　　if(L.r[j].key>L.r[j+1].key)
　　　　　　　　　　　swap(L.r[j],L.r[j+1]);
　　　　　　　　　　　change=true;
　　　　　　　}
　　　if(change==false) break;
　　　//一趟内循环未发生交换，则说明数组有序不需要进行之后循环，降低时间
　}
　return OK;
}

算法复杂度：$T(n)=O(n^2)$
优点：对于链表等结构有特有的优势

插入排序

算法思想：
　　若数据个数为n，以升序为例，则可认为第一个数据已经排序，只有循环比较之后的数据即可。暂存当次数据，是指与之前排序的结果（有序对）比较，在有序对中找到相应的插入位置，直至
结束

代码：

1
2
3
4
5
6
7
8
9
10
11
12
　Status InsertSort(SqList &L){
　//插入排序
　for(int i=2;i<=L.length;i++){
　　L.r[0]=L.r[i];	//复制为哨兵
　　int j;
　　for( j=i;j>=2&&L.r[0].key<L.r[j-1].key;--j){
　　　　L.r[j]=L.r[j-1];		//记录后移
　　}
　　L.r[j]=L.r[0];	//插入到正确位置
　}
　return OK;
}

算法复杂度：T(n)=O(n+I) I为逆序对个数

小结：每次交换的次数为逆序对个数
　　　同时，若I的个数较小，则可发现插入排序较好
　　　但是冒泡排序对于链表、数组等这种连续排列有其优势，而插入则没有
　　　缺点：每次只消除一个逆序对

希尔排序

算法思想：
　　　将序列分成若干子序列分别进行直接插入排序，比如五间隔、三间隔等等直至进行一间隔排序
定义增量序列：DM>DM-1>…>D1=1对每个Dk进行“Dk-间隔”排序(k=N,M-1,,…1)
Dk间隔排序后仍然保持Dk-1序列有序
原始希尔排序：
　　DM=floor(N/2),Dk=floor(Dk+1/2)
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
　Status ShellSort(SqList &L){
　//希尔排序　
　for(int D=L.length/2;D>0;D/=2)  //采用二分增量序列
　　　for(int i=D;i<=L.length;i++){
　　　　L.r[0]=L.r[i];	//复制为哨兵
　　　　int j;
　　　for( j=i;j>=D&&L.r[0].key<L.r[j-D].key;j-=D){
　　　　　L.r[j]=L.r[j-D];		//记录后移
　　　}
　　　L.r[j]=L.r[0];	//插入到正确位置
　}
　return OK;
}

选择排序

　算法思想：
　每次从i到length中找出最小值放在前面的有序序列中。
　代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
　Status SelectionSort(SqList &L){
　　//简单选择排序
　　for(int i=1;i<=L.length;i++){
　　　int min=i;
　　　for(int j=i;j<=L.length;j++){ //找出i至lenght的最小值
　　　　if(L.r[j].key<L.r[min].key)
　　　　　min=j;
　　　}
　　　if(i!=min)
　　　　swap(L.r[i],L.r[min]);
　　　//与插入类似，只不过找出余下的最小值放在前面作为有序队列
	}
　　return OK;
}

快速排序

　　算法思想：
　　　　一次快排：每次high从高位向前找到第一个比枢纽记录小的记录，交换low和high两记录，之后low从低位向高位找到第一个比枢纽记录大的记录，交换low和high两记录，直至最后high与low相等为止，完成一次快排，所得结果，枢纽左边的数都比它小，枢纽右边的数都比它大。
　　　　采用递归，对枢纽两边的序列二分，分两部分再次进行一次快排，以此类推，直至low与high相等

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int Partition(SqList &L,int low,int high) {
	//一次快排
	//int low = 1, high = L.length;
	//KeyType pivotkey = L.r[low].key;
	while (low < high) {
		while (low < high&&L.r[high].key >=/*pivotkey*/ L.r[low].key) --high;
		swap(L.r[low], L.r[high]);
		while (low < high&&L.r[low].key <=/*pivotkey*/ L.r[high].key) ++low;
		swap(L.r[low], L.r[high]);
	}
	return low;
}
Status QSort(SqList &L,int low,int high) {
　//快速排序
　//int low = 1, high = L.length;
　if (low < high) {
　　int pivotloc = Partition(L, low, high);
　　　QSort(L, low, pivotloc - 1);
　　　QSort(L, pivotloc + 1, high);
	}
　return OK;
}

堆排序

算法思想：
实质是对选择排序的改进。

堆的定义：n个元素的序列{k1,k2,…,kn}当且仅当满足下关系时，称之为堆
{ki<=k2i,ki<=k2i+1; 或 {ki>=k2i,ki>=k2i+1;

算法采用大顶堆排序，无序序列建堆就是一个反复筛选的过程。

一次筛选：将所有记录排列成完全二叉树形式，一次筛选从最后一个非终端节点（第floor(n/2)）开始，每次将当前结点的子树中最大记录与当前根结点交换，当前结点依次递减至根结点为止，交换根结点与最后一个结点的值。

代码：

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
typedef SqList HeapType;

Status HeapAdjust(HeapType &H, int s, int m) {
	//已知H.r[s..m]中记录的关键字除H.r[s].key之外均满足堆的定义，本函数调整H.r[s]
	//的关键字，使H.r[s..m]成为一个大顶堆（对其中记录的关键字而言）

	RedType rc = H.r[s];
	for (int j = 2 * s; j <= m; j * = 2) {   //沿key较大的孩子结点向下筛选
		if (j < m && H.r[j].key < H.r[j + 1].key) ++j; //j为key较大的记录的下标
		if (rc.key >= H.r[j].key) break;   //rc应插入在位置s上
		H.r[s] = H.r[j];
		s = j;
	}
	H.r[s] = rc;
	return OK;
}

Status HeapSort(HeapType &H) {
	//对顺序表H进行堆排序
	for (int i = H.length / 2; i > 0; --i)  //把H.r[1..H.length]建成大顶堆
		HeapAdjust(H, i, H.length);
	for (int i = H.length; i > 1; --i) {
		swap(H.r[1], H.r[i]);   //将堆顶记录和当前未经排序子序列Hr[1..i]中最后一个记录相互交换
		HeapAdjust(H, 1, i - 1);  //将H.r[1..i-1]重新调整为大顶堆
	}
	return OK;
}

归并排序

递归算法

基本思路
数组排序任务可以如下完成：
①把前一半排序
②把后一半排序
③把两半归并到一个新的有序数组，然后再拷贝回原数组，排序完成。

时间复杂度
时间复杂度：
T(n) = 2 * T(n / 2) + an
= 2 * (2 * T(n / 4) + an / 2) + an
= 4 * T(n / 4) + 2 * an
= 4 * (2 * T(n / 8) + an / 4) + 2 * an
= 8 * T(n / 8) + 3 * an
…
= 2 ^ kt(n / 2 ^ k) + kan

一直做到 n/2^k=1（此时k=log2(n)),
T(n) = 2^k * T(1) + k * a * n
=2^k * T(1) + k * a * n
=2^k + k * a * n
=n + a * n * log2(n)
复杂度$O(nlog n)$

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
/*
Copyright(c)2017, Louris
All	rights reserved.

文件名称：归并排序.cpp

解题思路：
数组排序任务可以如下完成：
①把前一半排序
②把后一半排序
③把两半归并到一个新的有序数组，然后再拷贝回原数组，排序完成。

时间复杂度：
T(n) = 2 * T(n / 2) + a*n
= 2 * (2 * T(n / 4) + a*n / 2) + a*n
= 4 * T(n / 4) + 2 * a*n
= 4 * (2 * T(n / 8) + a*n / 4) + 2 * a*n
= 8 * T(n / 8) + 3 * a*n
...
= 2 ^ k*t(n / 2 ^ k) + k*a*n

一直做到 n/2^k=1（此时k=log2(n)),
T(n) = 2^k * T(1) + k * a * n
=2^k * T(1) + k * a * n
=2^k + k * a * n
=n + a * n * log2(n)
复杂度O(nlog n)

当前版本：1.0
作    者：Louris
完成日期：2017.08.09
*/

#include<iostream>
using namespace std;
typedef int Status;
#define OK 1
#define ERROR 0

Status Merge(int a[], int low, int mid, int high, int temp[])
{
	//将数组a的局部a[low,mid]和a[mid+1,high]合并到temp，并保证temp有序，然后再拷贝回a[low,mid】
	//归并操作时间复杂度：O(high-mid+1)
	int pb = 0;
	int p1 = low, p2 = mid + 1;
	while (p1 <= mid&&p2 <= high)
	{
		if (a[p1] < a[p2])
		{
			temp[pb++] = a[p1++];
		}
		else
		{
			temp[pb++] = a[p2++];
		}
	}
	while (p1 <= mid)
	{
		temp[pb++] = a[p1++];
	}
	while (p2 <= high)
	{
		temp[pb++] = a[p2++];
	}
	for (int i = 0; i < high - low + 1; i++)
	{
		a[low + i] = temp[i];
	}
	return OK;
}

Status MergeSort(int a[], int low, int high, int temp[])
{
	if (low < high)
	{
		//int m = low + (high - low) / 2;
		int m = (low + high) / 2;
		MergeSort(a, low, m, temp);
		MergeSort(a, m + 1, high, temp);
		Merge(a, low, m, high, temp);
	}
	return OK;
}



int main()
{
	int a[10] = { 13,27,19,2,8,12,2,8,30,89 };
	int b[10];
	int size = sizeof(a) / sizeof(int);
	MergeSort(a, 0, size - 1, b);
	for (int i = 0; i < size; ++i)
	{
		cout << a[i] << ",";
	}
	cout << endl;

	return 0;
}

非递归算法

基本思路
k=2
先22归并
再44归并
…
注意剩余不足整数倍的剩余元素排序
代码

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
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

int main()
{
	int a[10] = { 13,27,19,2,8,12,2,8,30,89 };
	int n=10;
	int k=2;
	while(k<n)
	{
		for(int i=0;i<n/k;i++)
		{
			sort(a+i*k,a+(i+1)*k);
		}
		sort(a+n/k*k,a+n);
		k*=2;
	}
	for(int i=0;i<n;i++)
	{
		cout<<a[i];
		if(i!=n-1)
		{
			cout<<" ";
		}
	}
	return 0;
}
赏

Thank you for inviting me to have candy.

支付宝
微信

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

做一个安静细微的人，<br> 于角落里自在开放，<br> 默默悦人，<br> 却始终不引起过分热闹的关注，<br> 保有独立而随意的品格，<br> 这就很好。<br><br> Stick to what you insist on,<br> believe what you believe!<br> Life hastily for decades,<br> do what I can!