假期复习算法
先说下冒泡排序
冒泡排序
原理：比较两个相邻的元素，将值大的元素交换至右端。
思路：依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，
将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。重复第一趟步骤，直至全部排序完成。
第一趟比较完成后，最后一个数一定是数组中最大的一个数，所以第二趟比较的时候最后一个数不参与比较；
第二趟比较完成后，倒数第二个数也一定是数组中第二大的数，所以第三趟比较的时候最后两个数不参与比较；
依次类推，每一趟比较次数-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
| public class BubbleSort implements Sorter {
@Override
public int[] sort(int[] p) {
for (int i = 0; i < p.length - 1; i++) {
for (int j = 0; j < p.length - 1 - i; j++) {
if (p[j] > p[j + 1]) {
int temp = p[j];
p[j] = p[j + 1];
p[j + 1] = temp;
}
}
}
return p;
}
public static void main(String[] args) {
BubbleSort bubbleSort = new BubbleSort();
int []a = new int[]{9,8,7,6,5,4,3,1,2,0};
a=bubbleSort.sort(a);
bubbleSort.print(a);
}
}
|
快速排序
概念
快速排序（Quicksort）是对冒泡排序的一种改进。
快速排序由C.A.R.Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
快速排序也是一种采用分治法解决问题的一个典型应用，平均时间复杂度是O(nlogn)。在很多编程语言中，对数组，列表进行的非稳定排序在内部实现中都使用的是快速排序。
快速排序是通常被认为在同数量级 O(nlog2n)的排序方法中平均性能最好的。但若初始序列按关键码有序或基本有序时，快排序反而蜕化为冒泡排序。
为改进之，通常以“三者取中法”来选取基准记录，即将排序区间的两个端点与中点三个记录关键码居中的调整为支点记录。快速排序是一个不稳定的排序方法。
代码实现
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
| private void quickSortNormal(int []a,int s,int e){
if(s >= e){
return;
}
int base = a[s];
int left = s ,right = e;
while (left<right){
while(a[right] >= base && left < right){
right --;
}
a[left] = a[right];
while(a[left] <= base && left < right){
left ++;
}
a[right] = a[left];
}
a[left] = base;
quickSortNormal(a,s,left-1);
quickSortNormal(a,left+1,e);
}
|
改进一下减少交换次数
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
| private void quickSort(int []a,int s,int e){
if(s >= e){
return;
}
int base = a[s];
int left = s ,right = e;
while (left<right){
while(a[right] >= base && left < right){
right --;
}
while(a[left] <= base && left < right){
left ++;
}
if(left < right && a[left] > a[right]){
int t = a[right];
a[right] = a[left];
a[left] = t;
}
}
a[s] = a[left];
a[left] = base;
quickSort(a,s,left-1);
quickSort(a,left+1,e);
}
|
数组的常用技巧就是双指针。快排也是双指针处理的一种方案。
参考
快速排序——JAVA实现
https://blog.csdn.net/as02446418/article/details/47395867
必须知道的八大种排序算法 冒泡排序、快速排序
http://www.cnblogs.com/0201zcr/p/4763806.html