Algs4中基础排序的java代码实现

冒泡排序

特性:

  • 每两个元素进行比较,大的逐渐往一边移动
  • 最小(最大)的元素总是第一个被排好序,并集中在数组的末端(或者开始)

    基本写法:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    // 需要自己实现比较和交换函数
    public void bubblesort(Comparable[]a){
    int n = a.length;
    for(int i=0;i<n-1;i++){//记录已经排序的元素的数量
    for(int j=0;j<n-i-1;j++){//开始排序,除去了已经排序了的
    if(a[j]<a[j+1]){ //降序排列
    swap(a,j,j+1);
    }
    }
    }
    }
1
2
3
4
5
6
7
8
9
10
//比较函数参考
static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
//交换函数
static void exchange(Object[] a, int i, int j) {
Object swap = a[i];
a[i] = a[j];
a[j] = swap;
}

上面的写法是最开始能够想到的,但如果把排序过程打印出来的话,也可以用这个算法派有序的输入,就会发现重复排序的情况,就是说这个程序会一直执行下去,不管输入是否已经有序
bubble sort

要解决这个问题,需要加一个标志位,标识这个输入已经有序的

优化写法 参考了visuAlgo中的冒泡算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public void bubblesortX(Comparable[]a){
int n = a.length;
boolean swapped;//标志位,如果这个循环中,元素间没有发生交换则代表输入是有序的
for(int i=0;i<n-1;i++){
swapped = false;
for(int j=0;j<n-i-1;j++){
if(a[j]<a[j+1]){
swap(a,j,j+1);
swapped = true;//发生了交换,很有可能是乱序的
}
}
if(!swapped) break;//如果没有交换,则数组是有序的
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//visuAlgo 中的实现方法,循环关系更易理解
int n = a.length;
boolean swapped ;
int numOfSorted = 0; //记录已经排序的数量
do {
swapped = false;
for (int i = 0; i < n - numOfSorted-1; i++) {
if (less(a[i + 1], a[i])) {
exchange(a, i, i + 1);
swapped = true;
}
show(a);
}
numOfSorted++;
} while (swapped);

插入排序

概念及特点

  • 将当前元素插入到其他有序元素的恰当位置
  • 对已经排序(或接近排序)的数组进行排序,比随机,逆序的数组进行排序要快得多

    写法

    1
    2
    3
    4
    5
    6
    7
    8
    public static void InsertSort(Comparable[] a){
    int n = a.length;
    for(int i=0;i<n;i++){ //i代表当前准备要插入元素的位置
    for(int j=i;j>0&&less(a[j],a[j-1]);j--){
    exchange(a,j,j-1);
    }
    }
    }

优化

1
2
3
4
5
6
7
8
9
10
11
12
// 先为准备插入的元素准备好位置,实现了较大的元素右移一位只需访问一次数组
public static void InsertX(Comparable[] a){
int n = a.length;
for(int i=2;i<n;i++;){
Comparable temp = a[i];
int j =i;
while(j>0&&less(temp,a[j-1]){
a[j] = a[j-1];
}
a[j] = temp;
}
}

书中提到了一种规避边界测试的方法:插入排序的哨兵,使用时间比较的时候,发现效率降低了一点,不知道这种写法牺牲了效率,有什么好处?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int exchanges = 0; //交换次数
for (int i = n - 1; i > 0; i--) {
if (less(a[i], a[i - 1])) {
exchange(a, i, i - 1);
exchanges++;
}
}
if (exchanges == 0) return; // 没有发生交换则代表数组有序
for (int i = 2; i < n; i++) {
Comparable temp = a[i]; // 空间换时间
int j = i;
while (less(temp, a[j - 1])) {
a[j] = a[j - 1];
j--;
}
a[j] = temp;
}

上面的思想就是在有序的数组中提前找到合适的位置,让排序的元素放进去。这个找位置的过程还可以再优化一下。
有序数组中的查找可以使用二分查找写法如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static void BinaryInsertion(Comparable[] a) {
int n = a.length;
for (int i = 1; i < n; i++) {
int low = 0, high = i;
Comparable temp = a[i];
while (low<high){
int mid = (low+high)/2;
if (less(temp,a[mid])){
high = mid;
}else {
low = mid+1;
}
}
for (int j =i; j>low;j--){
a[j] = a[j-1];
}
a[low] = temp;
}
}

选择排序

特性

从一个无序的数组中找到最小(最大)的元素,并把它放在相应的位置(未排序的最后一个或第一个)即为每个位置找到相应的元素

写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
* 升序排序
* 假设辅助函数已经写好
*/
public static void SelectSort(Comparable[] a) {
int n = a.length;
for (int i = 0; i < n; i++) { //将要交换的位置
int min = i; // 假设当前位置为最小
for (int j = i + 1; j < n; j++) {
if (less(a[j], a[min])) {
min = j; // 如果找到更小的则更换下标
}
}
exchange(a, i, min);
}
}

实现简单,但每个位置都必须要找一次最小(最大),导致了如果输入是有序的话,还是需要比较过程找到最小的元素

希尔排序

概念

  • 让数组中的任意间隔为h的元素都是有序的
  • 按照一定步长来进行排序
  • 与插入排序相比: 交换不相邻的元素来对数组进行局部排序

    写法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    // 升序排列
    public static void ShellSort(Comparable[] a){
    int h = 1;
    while (h < n / 3) {
    h = 3 * h + 1; //经验证明:3*x+1 的间隔效果最好
    }
    while(h>=1){
    for(int i=h,i<n;i++){ //从最小满足间隔的元素开始,一直遍历到数组最后一个
    for(int j=i,j>=h&&less(a[i-h],a[i]),j-=h){
    //h数组内的排序,保证h数组是有序的
    // 如果j<h 则代表h数组没有了其他j上的元素,
    //如果没有发生交换代表h数组的其他元素是有序的,h数组排序完成
    //否则遍历下一个h数组里的元素
    exchange(a, j, j - h);
    }
    }
    h /=3;
    }
    }

以上所有算法代码来源于:算法第四版线上资料
算法可视化网站

接下里会有快速排序和合并排序的笔记