【算法】第二章：排序
【算法】第二章：排序
标签（空格分隔）：【Java算法】
第二章：排序
- 排序：将一组对象按照某种逻辑顺序重新排列的过程。
排序在计算机科学中占有极为重要的地位。
文章目录
2.1 初级排序算法
排序算法的目标是将所有元素的主键按照某种方式排序（通常是按照大小或字典序）。在Java中，元素通常是对象，对主键的抽象描述则是通过一种内置的机制。
下面给出排序类算法的模版：
public class Sort_Example {
public static void sort( Comparable[] a){
// such as: Insertion.sort(), Merge().sort, Quick.sort()等
}
private static boolean less( Comparable v, Comparable w){ //用来进行元素比较
return v.compareTo(w) < 0;
}
private static void exch( Comparable[] a, int i, int j){ //用来交换元素位置
Comparable t = a[i];
a[i] = a[j];
a[j] = t;
}
private static void show( Comparable[] a){
for( int i = 0; i < a.length; i++)
StdOut.print( a[i] + " ");
StdOut.println();
}
public static boolean isSort( Comparable[] a){
for( int i = 1; i < a.length; i++)
if( less( a[i], a[i-1]))
return false;
return true;
}
public static void main( String[] args){
String[] a = In.readStrings();
sort(a);
assert isSort(a);//为确保排序后的数组元素都是有序的
show(a);
}
}
//注意，这个类展示的只是数组排血实现的框架，并没有涉及到具体算法。
//注意，需要自己实现Compareble接口
- 运行时间：研究排序算法事，我们需要计算比较和交换的数量。对于不交换元素的算法，会计算访问数组的次数/
- 内存占用：1. 无需额外内存的原地排序算法；2. 需要额外内存空间的排序算法。
- 选择排序：该算法不断选择剩余元素的最小者，具体过程为：首先找到元素中最小的那个元素，将它和数组中的第一个元素交换位置；其次，在剩余元素中找到最小的元素与数组的第二个元素交换位置；如此往复，知道将整个数组排序。
运行时间：O(N^2).
内存占用：原地
特点；1. 运行时间与输入无关。如果输入为一个有序的数组或主键全部相等的数组情况下，与随机排列的数组耗时一样。2. 数据移动次数最少，每次交换只改变两个元素的值。
代码：
//将其代入到Sort_Example类中即可使用。
public static void Selection_sort( 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;
exch(a, i, min);
}
}
//输入： "SORTEXAMPLE"
//结果： "AEELMOPRSTX"
过程：
- 插入排序：索引左侧的所有元素是有序的，但是最终位置不确定。将右侧元素元素插入到已经有序的数组的适当位置。
运行时间：O(N^2).
内存占用：原地
特点：1.最好情况下（数组已经有序），运行时间为线性。同时，它对部分有序的数组十分高效。2. 适合小规模数组。
代码：
public static void sort( Comparable[] a){
int N = a.length;
for( int i = 1; i < N; i++){
for( int j = i; j > 0 && less( a[j], a[j - 1]); j--)
exch( a, j, j-1);
}
}
//输入： "SORTEXAMPLE"
//结果： "AEELMOPRSTX"
过程：
- 希尔排序：通过使数组中任意间隔为h的元素都是有序来完成排序。对于每一个h，用插入排序将h个自数组独立地排序。
运行时间：希尔排序是第一个打破 O(N^2) 的排序算法，最坏情况下为O(N^(3/2)). 其高效的原因在于它权衡了子数组的规模和有序性。
占用空间：原地
特点：1. 希尔排序基于插入排序。2. 适用于大型数组。3. 运行时间与 h 的选择有关，但在工程中影响不大。
代码：
public static void sort( Comparable[] a){
int N = a.length;
int h = 1;
while( h < N / 3)
h = 3 * h + 1; // h = 1, 4, 13, 40...
while( h >= 1){
for( int i = h ; i < N; i++)
for( int j = i; j >= h && less(a[j], a[j - h]); j-=h)
exch( a, j, j-h);
h = h/3;
}
}
//输入： "SHELLSORTEXAMPLE"
//结果： "AEEEHLLLMOPRSSTX"
过程：