有时候自己学了很久很久，学习的效果还是不好，慢慢反思，后来发现自己一直把大量的时间来学习新的知识，旧的知识基本上没有留什么时间来消化，最后的最后就是“感觉自己什么都学了，但是自己什么都不会”。学习有点乱的时候停一停，给了自己一些缓解的时间，找到问题的症结除治，然后努力在原有的基础上有新的突破……众所周知，我们学了很多的排序算法，真的学多了之后会特别的乱，所以特别的想花点时间整理一下O(∩_∩)O~
首先，是最简单的初级排序算法
1.选择排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| //选择排序的时间复杂度为O(n^2)；
//本排序是由小到大排的
void SelectionSort(int *arr,int n)
{
for(int i=0;i<n;i++)
{
int k=i; //假设最小元素就是为arr[0]
for(int j=i+1;j<n;j++) //从k下标后面的那个元素开始
{
if(arr[j]<arr[k])//如果j下标后面的数比arr[k]小
k=j; //改变最小元素下标
}
swap(arr[k],arr[i]);//第一轮找到数组中最小的元素，然后交换在第1位，第二轮放第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
| void insertsort(int *arr,int n)
{
for(int i=1;i<n;i++)//当前排序的元素下标
{
for(int j=i;j>0&&arr[j-1]>arr[j];j--)//最多执行到j=1与arr[0]比较，看是否需要交换位置；如果arr[j]前面的元素值一直比arr[j]值大，不断执行j--
{
swap(arr[j-1],arr[j]);
}
}
}
插入排序的优化
void Insertsort(int *arr,int n)
{
for(int i=1;i<n;i++)
{
int e=arr[i];
int j;
for(j=i;j>0&&arr[j-1]>e;j--)
{
arr[j]=arr[j-1]; //挪动一次的时间复杂度要优于交换一次的时间复杂度
}
arr[j]=e;
}
}
//插入排序对于最坏的情况虽然时间复杂度是O(n^2),但是插入排序对于近乎有序的数组来说，排序的效率非常之高，甚至比O(nlogn)的效率还要高；
|
此外还有一些初级的算法比如像”冒泡排序“，“希尔排序”…在此就不再列出了，因为它们的排序效率也不是很高
以下为时间复杂度为O(nlogn)的高级排序
3.归并排序
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
| void __Merge(int*arr,int l,int mid,int r)
{
int aux[r-l+1];
for(int i=l;i<=r;i++)
{
aux[i-l]=arr[i];
}
int i=l,j=mid+1;
for(int k=l;k<=r;k++)
{
if(i>mid) //左半部分元素已经全部处理完毕
{
arr[k]=aux[j-l];
j++;
}
else if(j>r) //右半部分元素已经全部处理完毕
{
arr[k]=aux[i-l];
i++;
}
else if(aux[i-l]<=aux[j-l]) //左半部分所指元素 <=右半部分所指元素,这里的等于号使得归并排序有了稳定性
{
arr[k]=aux[i-l];
i++;
}
else //左半部分所指元素 > 右半部分所指元素
{
arr[k]=aux[j-l];
j++;
}
}
}
void Mergesort(int *arr,int l,int r) //递归，此处的r为有效下标
{
if(l>=r)
return;
int mid=(r-l)/2+l;
Mergesort(arr,l,mid);
Mergesort(arr,mid+1,r);
if(arr[mid]>arr[mid+1])
__Merge(arr,l,mid,r);
}
void MergeSort(int *arr,int n) //此时的n为数组的最大下标数+1
{
Mergesort(arr,0,n-1);
}
|
4.快速排序
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
| //三路快排
void Quicksort(int *arr,int l,int r)
{
if(l>=r)
return ;
int v=arr[l];
int lt=l;
int gt=r+1;
int i=l+1;
while(i<gt)
{
if(arr[i]<v) //比v小的移到左边位置
{
swap(arr[i],arr[lt+1]);
i++;
lt++;
}
else if(arr[i]>v) //比v大的移到右边位置
{
swap(arr[i],arr[gt-1]);
gt--;
}
else //和v相等的不用移动，放在中间位置
{
i++;
}
}
swap(arr[l],arr[lt]); //这里不要写swap(v,arr[lt]);因为v和arr[l]地址不同，我们要做的是交换数组中两个元素的位置；
Quicksort(arr,l,lt-1);
Quicksort(arr,gt,r);
}
void QuickSort(int *arr,int n)
{
Quicksort(arr,0,n-1);
}
|
5.堆排序
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
| void shiftDown(int *data,int k,int count) //用来维护最大堆
{
while( 2*k <= count ){
int j = 2*k;
if( j+1 <= count && data[j+1] > data[j] ) j ++;
if( data[k] >= data[j] ) break;
swap( data[k] , data[j] );
k = j;
}
}
void MaxHeap(int *arr,int n ) //arr为用户传入的一个数组，n为数组的大小
{
int *data=new int [n+1];
for(int i=0;i<n;i++)
{
data[i+1]=arr[i];
}
for(int i=n/2;i>=1;i--) //从非叶子节点的元素开始进行shiftDown操作
{
shiftDown(data,i,n);
}
while(n>=1) //每次将堆中最大的那一个也就是data[1]给了arr[n-1](arr数组中倒数第一、倒数第二...的位置)
{
arr[n-1]=data[1];
swap(data[1],data[n]);
n--; //每次传出了一个元素后n需减一
shiftDown(data,1,n);
}
delete []data;
}
------------------------------------------------------
//1.以上完成了第一种方式的堆排序⤴️
//2.下面来实现下第二种方式的堆排序，大同小异，没有开辟额外的空间，直接是原地堆排序，性能上稍微好了点⬇️
-----------------------------------------------------
void shiftDown(int *data,int k,int count)
{
while( 2*k+1<count ){
int j = 2*k+1;
if( j+1 < count && data[j+1] > data[j] ) j ++;
if( data[k] >= data[j] ) break;
swap( data[k] , data[j] );
k = j;
}
}
void MaxHeap(int *arr,int n )
{
for(int i=(n-2)/2;i>=0;i--)
{
shiftDown(arr,i,n);
}
for(int i=n-1;i>=0;i--) {
swap(arr[0],arr[i]);
shiftDown(arr, 0, i);
}
}
|
几种排序算法的性能
当然还有许多的排序，比如桶排序、shellsort等等，我就不继续写了，毕竟在涉及排序问题的算法时我们只会选择一类来进行解题(我个人是这么理解的…)排序算法看似简单，即使这样我们在考虑数组下标的时候也要注意，谨防越界，不然debug真的会很痛苦的。我在写这几个排序算法的时候同样我又发现了好几个自身的问题，真的是复习旧的知识确实能发现新大陆。同时在这里也要感谢bobo老师的教学指导，他的课让我受益匪浅——蒻蒻的我，继续加油吧！
