放假了比较有空,就整理了一下排序上的一些算法(。・ω・。)ノ♡
1.冒泡排序
- 思想
从第一项开始与后一项相比较,如果发现大(小)的就交换
交换的对数会随次数即i的增加而减少
每做完一次循环,最后的一个数是最大(小)的数 - 特点:>_容易理解,_**但是真的超级慢**
用快排它不舒服吗
下面是代码
1 | void bubblesort(int a[], int n) { |
2.选择排序
- 思想
在没有排好的队列中找到最小(大)的元素,放到最前面即起始位置
在剩余未排好序列中寻找最小(大)的元素,放到已排好的序列的末尾eg:2 1 3 4 2 9 -> 1 2 3 4 2 9
- 下面贴上代码3.快速排序(参考了一下洛谷的快排模板)
1
2
3
4
5
6
7
8
9
10
11
12
13
14void selectionsort(int a[], int n) {
int midindex, temp;
for(int i = 0 ; i < n ; i++ ) {
midindex = i;
for(int j = i + 1 ; j < n ; j++ ) {
if(a[midindex] > a[j] ) {
midindex = j ;
}
}
temp = a[midindex] ;
a[midindex] = a[i] ;
a[i] = temp;
}
}- 特点:
非常快,可以试一下逃TLE _
_比较复杂 ,比较容易写错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
30void quicksort(int *a,int left,int right) {
if(left > right)
return ;
//如果是左边比右边大可以直接结束进程
int i = left, j = right ;
int mid = a[(left+right)/2];
//mid其实是作为一个检测的点
while( i <= j ) {
while(a[j] > mid) {
j--;
}
while(a[i] < mid) {
i++;
}
//左边的往右边走,右边的往左边走
if(i <= j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
i++;
j--;
}
if(i < right ) {
quicksort(a,i,right);
}
if(j > left) {
quicksort(a,j,left);
}
}
}
- 特点: