排序算法

插入排序

直接插入排序

基本思想:
我们将一个待排序序列分为有序区和无序区(一般开始的时候将第一个元素作为有序区,剩下的元素作为无序区),每次将无序区的第一个元素作为待插入记录,按大小插入到前面已经排好的有序区中的适当位置,直到记录全部插入完成为止。(如果待插入的元素与有序序列中的某个元素相等,则将待插入元素插入到相等元素的后面)

C++实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void insert_sort_1(int a[],int n)//对n个元素从小到大排序
{
int i,j;
int temp;
for(i=1;i<n;i++)
{
temp = a[i];//待插入元素
j = i-1;
while(temp<a[j] && j)
{
a[j+1] = a[j];//将大的往后挪
j--;//顺利的话可以减到-1,要么就是减到可以插入的位置的前一个位置
//所以后面的j需要加1
}
a[j+1]=temp;
}
}

C++实现_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
#include<iostream>
using namespace std;

void insert_sort_2(int a[],int n)//n个数,排的实际上是下标为1到n-1的元素,a[0]是监视哨
{
int i,j;
//初始状态下a[1]为初始有序区
//a[2]到a[n-1]为无序区
for(i=2;i<n;i++)
{
a[0] = a[i];//设置监视哨
j = i-1;
while(a[0]<a[j])//将有序区中大于监视哨的元素往后挪,没有就不动
{
a[j+1] = a[j];
j--;//如果顺利可以减到0下标
}
a[j+1] = a[0];
}
}

int main()
{
int temp[11]={0,10,9,8,7,6,5,4,3,2,1};//真正用于排序的只有10个数
insert_sort_2(temp,11);
for(int i=1;i<11;i++)
{
cout<<temp[i]<<endl;
}
return 0;
}

直接选择排序

冒泡排序

基本思想:
我们把待排序元素序列竖直放置,每趟对相邻的元素进行两两比较,顺序相反则进行交换,每趟会将最小或最大的元素“浮”到元素序列的顶端,最终元素序列达到有序

C++实现

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

void bubble_sort(int array[],int n)//对n个数从小到大排序,注意数组下标从0开始
{
int i,j;
int temp;
for(i=0;i<n-1;i++)//进行n-1趟比较
{
for(j=0;j<n-1-i;j++)//每趟进行n-1-i次比较
{
if(array[j+1]<array[j])
{
temp = array[j+1];
array[j+1] = array[j];
array[j] = temp;
}
}
}
}


int main()
{
int a[10] = {10,9,7,8,6,5,4,2,3,1};
bubble_sort(a,10);
for(int i=0;i<10;i++)
{
cout<<a[i]<<" ";
}
return 0;
}

快速排序

快速排序是分治思想在排序算法上的应用,从本质上来讲快速排序应该是在冒泡排序基础上的递归分治法。

算法步骤:

  1. 从待排数列中选出一个元素作为基准,一般选第一个元素
  2. 重新排序待排数列,所有元素比基准小的摆放在基准前面,所有元素比基准大的摆放在基准后面(相同的数可以放在任意一边)。在这个分区退出后,该基准就处于中间位置。(这个即为分区操作(partion))。
  3. 递归地把小于基准元素的子数列和大于基准元素的子数列进行排序。

quickSort.gif

C实现

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
#include<stdio.h>
int a[101],n;

void quick_sort(int left, int right)
{
int i,j,temp;
int t;
if(left > right)
{
return ;
}

temp = a[left];//基准数


i = left;
j = right;
while(i != j)
{
//顺序很重要,先从右往左找
while( a[j] >= temp && i<j)
{
j--;
}

//再从左边往右找
while( a[j] <= temp && i<j)
{
i++;
}

//交换两个数在数组中的位置
if(i<j)//两个哨兵没有相遇
{
t = a[i];
a[i] = a[j];
a[j] = t;
}
}

//最终将基准数归位,

a[left] = a[i];

a[i] = temp;//归位

quick_sort(left,i-1);//继续处理左边的数
quick_sort(i+1,right);//继续处理右边的数

return ;
}

int main()
{
int i,j;
scanf("%d",&n);
for(i=1; i<=n; i++)//下表从1开始
scanf("%d",&a[i]);

quick_sort(1,n);//sort

for(j=1; j<=n; j++)
printf("%d ",a[j]);

return 0;
}

参考:

https://blog.csdn.net/adusts/article/details/80882649

https://github.com/hustcc/JS-Sorting-Algorithm

 评论


博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本站使用 Material X 作为主题 , 总访问量为 次 。