Chen's Blog HomeArchivesTagsCategories
排序算法总结

1 前言

总结一下,最近老师上课讲的排序算法……毕竟上课没认真听,就得自己花点时间了…..

参考:https://blog.csdn.net/dongfei2033/article/details/79938651

1574086817059

2 排序算法

2.1 冒泡排序

2.1.1 数组实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void bublletSort(int a[],int len)
{
  int temp;
  for(int i=0;i<len-1;i++)
  {
     for(int j=0;j<len-i;j++)
     {
        if(a[j]>a[j+1])
        {
           temp = a[j];
           a[j] = a[j+1];
           a[j+1] = temp;
        }
     }
  }
}

2.1.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
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
101
102
103
104
105
106
#include <iostream>
#include <cstring>
#include<typeinfo>
using namespace std;

#define END_CODE -999 //链表结点'数据录入'结束标志！

/*(0)元素(结点)类型 */
/*(0.1)单一元素 */
typedef  int  ElemType;

/*(0.2)混合元素 -> 通过结构体进行定义 */
//typedef struct { //此部分：根据实际问题进行定义...
//	float  coef;   /*系数部分*/
//	int    expn;   /*指数部分*/
//} ElemType;

/*(1)单链表结点 定义*/
typedef  struct  lnode {
	ElemType  data;     //数据域
	struct  lnode  *next;      //指针域
} LNode; /*结点的类型 */

void show(LNode *L); //函数声明

/*(2.1)【头插入法】创建单链表,链表的头结点head作为返回值 */
LNode *create_LinkList_H( ) {
	LNode *head, *q; //head-头结点; q-待插入结点指针

	//(A)创建只有头结点head的: '空单链表'
	head = new LNode; //head = (LNode *) malloc( sizeof(LNode) );
	head->next = NULL;

	//(B)录入链表各结点的数据, 并钩链
	ElemType data;  //线性表 结点的数据域
	cout<<"input data : "<<END_CODE<<" to stop!\n";
	while( true ) { //无限循环, 只到停止输入...
		//(a)键盘输入一个链表结点数据-->data
		cin >> data; //scanf("%d", &data);

		//(b)若录入数据data == '数据录入'结束标志END_CODE,则完成链表创建！
		if( data == END_CODE ) {
			break;
		}

		//(c)录入的链表结点数据'data'有效, 则创建一个链表结点存储此数据
		q = new LNode; //q = (LNode *)malloc(sizeof(LNode)); //新建'链表结点'
		q->data = data;	//数据域赋值

		//(d)钩链: 新创建的结点q总是作为第一个结点
		q->next = head->next;
		head->next = q;

		//(e)信息提示: 结点创建成功! 并显示当前链表的内容信息！！！
		cout << "Node" << q->data << "create successfully!\n";
		//show(head); //显示当前的链表
	}

	//(C)返回此单链表的'头结点head'
	return (head);
}

void BubbletSort(LNode *head)//简单选择排序
{
	LNode *p,*q;
	int s;
    for(p=head->next;p!=NULL;p=p->next)
      for(q=p->next;q!=NULL;q=q->next)
        if((p->data)>(q->data))
         {
            s=p->data;
            p->data = q->data;
            q->data = s;
         }
}



void show(LNode *L) {
	//(A)单链表为NULL空
	if(L->next == NULL) {
		cout << "linklist: empty!!!\n";
		return;
	}

	//(B)输出以L为头结点的单链表的各个结点的数据格式:"顺序表:-->e1->e2->...->en"
	LNode *q = L->next; //q指向L的下一结点
	cout << "number: ";
	while(q != NULL) { //循环,以输出各结点的数据
		//(a)输出结点数据
		cout << " " << q->data;

		//(b)下一个结点
		q = q->next;
	}
	cout << endl; //链表输出结束-换行
}

int main()
{
    LNode *head = create_LinkList_H();
    show(head);
    BubbletSort(head);
    show(head);
    return 0;
}

2.2 插入排序

2.2.1 数组实现

原理参考链接:直接插入排序(数组实现)

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
#include<iostream>
#include<cstdlib>

using namespace std;

void insertSort(int a[],int n)
{
   for(int i=1;i<n;i++)
   {
      int key=a[i];//key 为哨兵 待插入的数据放入哨兵中
      int j=i-1;
      while(j>=0&&a[j]>key)//从哨兵开始从右往左开始遍历
      {
         a[j+1] = a[j];//数据往后移动一个位置
         j--;//从key开始遍历,j--表示往前移动一个位置,直至寻找到一个a[j]小于key
      }
      a[j+1] = key;
   }
}


int main()
{
	int a[] = { 2,1,4,5,3,8,7,9,0,6 };

	int n=10;
	insertSort(a,n);

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

	}
	cout << endl;
	return 0;

}

2.2.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
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
101
#include <iostream>
#include <cstring>
#include<typeinfo>
using namespace std;

#define END_CODE -999 //链表结点'数据录入'结束标志！

typedef  int  ElemType;

/*(1)单链表结点 定义*/
typedef  struct  lnode {
	ElemType  data;     //数据域
	struct  lnode  *next;      //指针域
} LNode; /*结点的类型 */

void show(LNode *L); //函数声明

/*(2.1)【头插入法】创建单链表,链表的头结点head作为返回值 */
LNode *create_LinkList_H( ) {
	LNode *head, *q; //head-头结点; q-待插入结点指针

	//(A)创建只有头结点head的: '空单链表'
	head = new LNode; //head = (LNode *) malloc( sizeof(LNode) );
	head->next = NULL;

	//(B)录入链表各结点的数据, 并钩链
	ElemType data;  //线性表 结点的数据域
	cout<<"input data : "<<END_CODE<<" to stop!\n";
	while( true ) { //无限循环, 只到停止输入...
		//(a)键盘输入一个链表结点数据-->data
		cin >> data; //scanf("%d", &data);

		//(b)若录入数据data == '数据录入'结束标志END_CODE,则完成链表创建！
		if( data == END_CODE ) {
			break;
		}

		//(c)录入的链表结点数据'data'有效, 则创建一个链表结点存储此数据
		q = new LNode; //q = (LNode *)malloc(sizeof(LNode)); //新建'链表结点'
		q->data = data;	//数据域赋值

		//(d)钩链: 新创建的结点q总是作为第一个结点
		q->next = head->next;
		head->next = q;

		//(e)信息提示: 结点创建成功! 并显示当前链表的内容信息！！！
		cout << "Node" << q->data << "create successfully!\n";
		//show(head); //显示当前的链表
	}

	//(C)返回此单链表的'头结点head'
	return (head);
}

void InsertSort(LNode *L){
   LNode *p,*r,*q;
   p=L->next;
   q=p->next;//q保存p的后继
   p->next=NULL;
   p=q;
   while(p!=NULL){
     q=p->next;
     r=L;
     while(r->next!=NULL&&r->next->data<p->data){
        r=r->next;
     }
     p->next = r->next;
     r->next = p;
     p=q;
   }
}

void show(LNode *L) {
	//(A)单链表为NULL空
	if(L->next == NULL) {
		cout << "linklist: empty!!!\n";
		return;
	}

	//(B)输出以L为头结点的单链表的各个结点的数据格式:"顺序表:-->e1->e2->...->en"
	LNode *q = L->next; //q指向L的下一结点
	cout << "number: ";
	while(q != NULL) { //循环,以输出各结点的数据
		//(a)输出结点数据
		cout << " " << q->data;

		//(b)下一个结点
		q = q->next;
	}
	cout << endl; //链表输出结束-换行
}


int main()
{
    LNode *head = create_LinkList_H();
    show(head);
    InsertSort(head);
    show(head);
    return 0;
}

2.3 选择排序

2.3.1 数组实现

原理参考:选择排序(数组实现)

实际上选择排序是冒泡排序的升级版…..

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void selectSort(int a[],int len)
{
   int minindex,temp;//minindex-哨兵  temp-暂存空间
   for(int i=0;i<len;i++)
   {
      minindex=i;//设置哨兵为当前位置元素
      for(int j=i+1;j<len;j++)
      {
         if(a[j]<a[minindex]) minindex=j;//从左往右遍历哨兵(当前位置元素)往右的元素
                                         //找到比哨兵(当前位置元素)小的元素,把哨兵的位置让给它
                                         //找到的这个元素是数组中最小的元素
      }
      
      //a[i]与哨兵(最小的元素)交换位置
      temp = a[i];//a[i]为当前位置的元素,temp为暂存空间
      a[i] = a[minindex];
      a[minindex] = temp;
   }
}

2.3.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
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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <iostream>
#include <cstring>
#include<typeinfo>
using namespace std;

#define END_CODE -999 //链表结点'数据录入'结束标志！

/*(0)元素(结点)类型 */
/*(0.1)单一元素 */
typedef  int  ElemType;

/*(0.2)混合元素 -> 通过结构体进行定义 */
//typedef struct { //此部分：根据实际问题进行定义...
//	float  coef;   /*系数部分*/
//	int    expn;   /*指数部分*/
//} ElemType;

/*(1)单链表结点 定义*/
typedef  struct  lnode {
	ElemType  data;     //数据域
	struct  lnode  *next;      //指针域
} LNode,*LinkList; /*结点的类型 */

void show(LNode *L); //函数声明

/*(2.1)【头插入法】创建单链表,链表的头结点head作为返回值 */
LNode *create_LinkList_H( ) {
	LNode *head, *q; //head-头结点; q-待插入结点指针

	//(A)创建只有头结点head的: '空单链表'
	head = new LNode; //head = (LNode *) malloc( sizeof(LNode) );
	head->next = NULL;

	//(B)录入链表各结点的数据, 并钩链
	ElemType data;  //线性表 结点的数据域
	cout<<"input data : "<<END_CODE<<" to stop!\n";
	while( true ) { //无限循环, 只到停止输入...
		//(a)键盘输入一个链表结点数据-->data
		cin >> data; //scanf("%d", &data);

		//(b)若录入数据data == '数据录入'结束标志END_CODE,则完成链表创建！
		if( data == END_CODE ) {
			break;
		}

		//(c)录入的链表结点数据'data'有效, 则创建一个链表结点存储此数据
		q = new LNode; //q = (LNode *)malloc(sizeof(LNode)); //新建'链表结点'
		q->data = data;	//数据域赋值

		//(d)钩链: 新创建的结点q总是作为第一个结点
		q->next = head->next;
		head->next = q;

		//(e)信息提示: 结点创建成功! 并显示当前链表的内容信息！！！
		cout << "Node" << q->data << "create successfully!\n";
		//show(head); //显示当前的链表
	}

	//(C)返回此单链表的'头结点head'
	return (head);
}

void SelectSort(LinkList &L)//简单选择排序
{
   LinkList p = L->next;
   LinkList minindex;//设置一个节点minindex
   LinkList q;
   int temp;
   while(p)//从第一个节点开始遍历
   {
     q=p->next;//第一个节点往右的节点
     minindex=p;//设置当前ｐ指针为最小，为这一趟选择排序开始的位置
     while(q)//
     {
       if(q->data<minindex->data) minindex=q;//在本趟中寻找最小的那个数

       q=q->next;
       if(minindex!=p)//判断最小的数是否为当前的节点ｐ
       {
         temp = minindex->data;
         minindex->data = p->data;
         p->data = temp;
       }
     }
     p=p->next;
   }
}

void show(LNode *L) {
	//(A)单链表为NULL空
	if(L->next == NULL) {
		cout << "linklist: empty!!!\n";
		return;
	}

	//(B)输出以L为头结点的单链表的各个结点的数据格式:"顺序表:-->e1->e2->...->en"
	LNode *q = L->next; //q指向L的下一结点
	cout << "number: ";
	while(q != NULL) { //循环,以输出各结点的数据
		//(a)输出结点数据
		cout << " " << q->data;

		//(b)下一个结点
		q = q->next;
	}
	cout << endl; //链表输出结束-换行
}


int main()
{
    LNode *head = create_LinkList_H();
    show(head);
    SelectSort(head);
    show(head);
    return 0;
}

2.4 快速排序

2.4.1 数组实现

原理参考:快速排序原理

代码参考如下:

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
#include<iostream>
#include<cstdlib>

using namespace std;

void quickSort(int a[],int left,int right)
{
  int i,j,t,temp;
  if(left>=right) //作为后面递归结束的判断依据
     return;
  temp=a[left];//temp为基准数,该
  i=left;//i相当于左边的哨兵
  j=right;//j相当于右边的哨兵
  while(i!=j)
  {
     //从右往左开始寻找比temp小的数,直至找到为止
     while(a[j]>=temp&&i<j) j--;
    
     //从左往右开始寻找比temp大的数,直至找到为止
     while(a[i]<=temp&&i<j) i++;
     if(i<j)//交换位置
     {
       t=a[i];
       a[i]=a[j];
       a[j]=t;
     }
  }
  a[left]=a[i];//基准数归位
  a[i]=temp;
  quickSort(a,left,i-1);
  quickSort(a,i+1,right);
}

int main()
{
	int a[] = { 3,1,4,5,2,8,7,9,6,0 };

	int n=10;
	quickSort(a,0,9);

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

	}
	cout << endl;
	return 0;
}
Author: 我是小吴啦
Link: http://yoursite.com/2019/11/19/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E6%80%BB%E7%BB%93/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
算法,操作系统