排序算法
排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。
排序算法情况比较
冒泡排序
基本思想
两个数比较大小，较大的数下沉，较小的数冒起来。
过程
- 比较相邻的两个数据，如果第二个数小，就交换位置。
- 从后向前两两比较，一直到比较最前两个数据。最终最小数被交换到起始的位置，这样第一个最小数的位置就排好了。
- 继续重复上述过程，依次将第2.3...n-1个最小数排好位置。
执行图解如图
代码
1
2
3
4
5
6
7
8
9
10
11
| public static void BubbleSort(int[] arr){
for(int i=0;i<arr.length;i++){
for(int j=0;j<arr.length-i-1;j++){
if (arr[j] > arr[j + 1]){
int temp = arr[j+1];
arr[j+1]=arr[j];
arr[j]=temp;
}
}
}
}
|
优化
问题
数据的顺序排好之后，冒泡算法仍然会继续进行下一轮比较，直到arr.length-1次，但后面的比较没有意义
方案
设置标志位flag，如果发生了交换flag设置为true；如果没有交换就设置为false。
这样当一轮比较结束后如果flag仍为false，即：这一轮没有发生交换，说明数据的顺序已经排好，没有必要继续进行下去。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| public static void BubbleSort(int[] arr){
boolean flag;
for(int i=0;i<arr.length;i++){
flag = false;
for(int j=0;j<arr.length-i-1;j++){
if (arr[j] > arr[j + 1]){
int temp = arr[j+1];
arr[j+1]=arr[j];
arr[j]=temp;
flag = true;
}
}
if(!flag){
break;
}
}
}
|
选择排序
基本思想
在长度为N的无序数组中，第一次遍历n-1个数，找到最小的数值与第一个元素交换；
第二次遍历n-2个数，找到最小的数值与第二个元素交换；
。。。
第n-1次遍历，找到最小的数值与第n-1个元素交换，排序完成。
过程
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| public static void SelectSort(int[] arr) {
for (int i = 0; i < arr.length; i++) {
int min = i;
int value = arr[i];
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[i] && arr[j] < value) {
min = j;
value = arr[j];
}
}
final int temp = arr[min];
arr[min] = arr[i];
arr[i] = temp;
}
}
|
插入排序
基本思想
在要排序的一组数中，假定前n-1个数已经排好序，现在将第n个数插到前面的有序数列中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。
过程
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
| public static void InsertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
for (int j = i; j > 0; j--) {
if (arr[j] < arr[j - 1]) {
int temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
} else {
break;
}
}
}
}
|
希尔排序
基本思想
在要排序的一组数中，根据某一增量分为若干子序列，并对子序列分别进行插入排序。
然后逐渐将增量减小,并重复上述过程。直至增量为1,此时数据序列基本有序,最后进行插入排序。
过程
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| public static void HellSort(int[] arr){
int gap = 4;
while(gap>0) {
for (int i = gap; i < arr.length; i+=gap) {
for (int j = i; j > 0; j-=gap) {
if (arr[j] < arr[j - gap]) {
int temp = arr[j - gap];
arr[j - gap] = arr[j];
arr[j] = temp;
} else {
break;
}
}
}
gap/=2;
}
|
快速排序
基本思想
- 先从数列中取出一个数作为key值；
- 将比这个数小的数全部放在它的左边，大于或等于它的数全部放在它的右边；
- 对左右两个小数列重复第二步，直至各区间只有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
| public static void FastSort(int[] arr, int low, int high){
if(low>high){
return ;
}
int i = low;
int j = high;
int pivot = arr[i];
while(i<j){
while(i<j && arr[j]>=pivot){
j--;
}
if(i<j){
arr[i] = arr[j];
i++;
}
while(i<j && arr[i]<=pivot){
i++;
}
if(i<j){
arr[j] = arr[i];
j--;
}
}
arr[i] = pivot;
FastSort(arr, low, i-1);
FastSort(arr, i+1, high);
}
|
归并排序
堆排序
基数排序
