本文總結(jié)算法第四版中幾大基本排序算法的實現(xiàn)丧失，用Java語言描述。文章結(jié)構(gòu)安排如下：
1.通用模板介紹
2.插入排序
3.選擇排序
4.希爾排序
5.歸并排序
6.快速排序
7.冒泡排序
通用模板介紹
通用模板將排序算法中的基本操作做了封裝奖慌，如交換元素镐躲、比較元素大小等，可以使排序算法的主函數(shù)邏輯更簡潔岩睁，增加代碼的可讀性歧寺。
public class Example {
//交換兩個元素
public static void exch(Comparable[] a,int i,int j) {
Comparable temp = a[i];
a[i]=a[j];
a[j]=temp;
}
//從小到大排列
public static boolean less(Comparable v,Comparable w) {
return v.compareTo(w)<0;
}
//打印全部元素
public static void show(Comparable [] a) {
for(int i=0;i<a.length;i++)
System.out.print(a[i]+" ");
System.out.println();
}
//判斷是否已經(jīng)有序
public static boolean isSorted(Comparable [] a) {
for(int i=1;i<a.length;i++) {
if(less(a[i], a[i-1])) return false;
}
return true;
}
}
插入排序
插入排序的操作設(shè)置兩個掃描指針燥狰，i指針在外層循環(huán)，掃描方向為下標(biāo)遞增方向斜筐，指向的元素代表：此時為該元素尋找插入位置碾局。j指針在內(nèi)層循環(huán)，掃描方向與i指向元素相反奴艾。
public static void InsertSort(Comparable[] a) {
int N = a.length;
for(int i=1;i<a.length;i++) {
for(int j=i;j>0 && less(a[j],a[j-1]);--j)
exch(a, j, j-1);
}
}
public static void insert_sort(int[] arr) {
if(arr == null || arr.length ==0) return;
for(int i=1;i<arr.length;i++) { //arr[i]是待插入元素
for(int j=i;j>0 && arr[j] < arr[j-1];--j) { //將arr[i]插入arr[i-1],arr[i-2]..中
int temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
}
}
}
選擇排序
選擇排序有兩層循環(huán)净当，算法的核心思想是，每一輪循環(huán)都將當(dāng)前最小的元素放在正確的位置上。外層循環(huán)的指針指向當(dāng)前排序的位置像啼，內(nèi)層循環(huán)負責(zé)尋找當(dāng)前最小的元素俘闯。
public static void SelectSort(Comparable[] a) {
int min=0;
int N = a.length;
for(int i=0;i<N;i++) {
min=i;
for(int j=i;j<N;j++) {
if(less(a[j], a[min])) min=j;
}
exch(a, i, min);
}
}
//選擇排序，每次從當(dāng)前序列中忽冻，選出最小的那個放在正確的位置上
public static void select_sort(int[] arr) {
if(arr == null || arr.length ==0) return;
for(int i=0;i<arr.length-1;i++) {
int min = i; //當(dāng)前最小元素的位置
for(int j=i+1;j<arr.length;j++)
if(arr[j] < arr[min]) min = j;
if(min!=i) {
int temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
}
}
希爾排序
根據(jù)步長將待排數(shù)組劃分為若干組真朗，然后組內(nèi)交換排序。
image.png
image.png
image.png
public static void ShellSort(Comparable[] a) {
int N = a.length;
for(int h=N/2;h>0;h/=2)
for(int i=h;i<N;i++)
for(int j=i;j>=h && less(a[i],a[j-h]);j-=h)
exch(a, i, j-h);
}
//希爾排序
public static void shell_sort(int[] arr) {
if(arr == null || arr.length ==0) return;
for(int h = arr.length/2;h>=1;h/=2) { //步長h
for(int i=h;i<arr.length;i++) { //每一組的最后一個元素 arr[i]為待插入元素
for(int j=i-h;j>=0;j-=h) { //比較 arr[i-h],arr[i-2h],arr[i-3h]...
if(arr[j+h] < arr[j]) {
int temp = arr[j];
arr[j] = arr[j+h];
arr[j+h] = temp;
}
}
}
}
}
歸并排序
本文介紹自頂向下的歸并排序僧诚，采用遞歸方法實現(xiàn)遮婶，需要輔助數(shù)組aux[]。
private static void sort(Comparable []a,int low,int high) {
if(low>=high) return;
int mid = (low+high)/2;
sort(a,low, mid);
sort(a, mid+1, high);
merge(a, low, mid, high);
}
//兩個數(shù)組歸并
private static void merge(Comparable [] a,int low,int mid,int high) {
int i = low;
int j = mid+1;
int k;
for(k=low;k<=high;k++) aux[k]=a[k];
for(k=low;k<=high;k++) {
if(i>mid) a[k]=aux[j++];
else if(j>high) a[k]=aux[i++];
else if(less(a[j], a[i])) a[k]=a[j++];
else a[k]=a[i++];
}
}
public static void sort(Comparable[] a) {
aux = new Comparable [a.length];
sort(a, 0, a.length-1);
}
算法實現(xiàn)
class MergeSort
{
static int[] aux = null;
public static void main(String[] args)
{
int[] arr = {3,1,2,5,4,6,0,9,1,3};
aux = new int[arr.length];
merge_sort(arr);
for(int tmp:arr)
System.out.print(tmp+" ");
System.out.println();
}
public static void merge_sort(int[] arr) {
if(arr == null || arr.length ==0) return;
merge_sort(arr,0,arr.length-1);
}
private static void merge_sort(int[] arr, int low, int high) {
if(low >= high) return; //返回條件 取=湖笨，單個元素的時候不用排序
int mid = (low + high)/2;
merge_sort(arr,low,mid);
merge_sort(arr,mid+1,high);
merge(arr,low,mid,high);
}
private static void merge(int[] arr,int low,int mid,int high) {
if(low >= high) return;
for(int k = low;k<=high;k++) //每次merge都要復(fù)制aux
aux[k] = arr[k];
int i=low,j = mid+1;
for(int k=low;k<=high;k++) {
if(i>mid) arr[k] = aux[j++];
else if(j>high) arr[k] = aux[i++]; //注意是else if
else if(aux[i] < aux[j]) arr[k] = aux[i++];
else arr[k] = aux[j++];
}
}
}
快速排序
快速排序的核心函數(shù)是partition旗扑，用于確定分割點，然后分別對分割點左邊和右邊sort排序慈省⊥畏溃快排設(shè)置頭、尾兩個指針i和j边败，相向而行進行掃描袱衷，以及一個比較標(biāo)準(zhǔn)val（通常為arr[low]）。
private static void sort(Comparable[] a,int low,int high) {
if (high <= low) return;
int j = partition(a, low, high);
sort(a, low, j-1);
sort(a, j+1, high);
}
private static int partition(Comparable a[],int low,int high) {
//兩個指針
int i = low;
int j = high+1;
Comparable v = a[low];
while(true) {
while(less(a[++i],v)) if(i==high) break;
while(less(v, a[--j])) if(j==low) break;
if(i>=j) break; //次輪結(jié)束標(biāo)志
exch(a, i, j);
}
exch(a, low, j);
return j;
}
public static void sort(Comparable[] a) {
sort(a,0,a.length-1);
}
具體實現(xiàn)笑窜。
//整合優(yōu)化
public static void quick_sort(int[] arr,int low,int high) {
if(low >= high) return;
//int j = partition(arr,low,high);
int i=low, j = high;
int x = arr[low]; //Pivot
while(i<j) {
while(i<j && arr[j]>=x) --j; //從后向前找小于x的元素
if(i<j) {
arr[i] = arr[j]; //填數(shù)
++i;
}
while(i<j && arr[i]<=x) ++i;
if(i<j) {
arr[j] = arr[i];
--j;
}
}
arr[i] = x;
quick_sort(arr,low,j-1);
quick_sort(arr,j+1,high);
}
冒泡排序
冒泡排序總是交換兩個相鄰的元素致燥。每一輪冒泡，都將當(dāng)前最小的元素固定在數(shù)組前列排截。
public static void bubble_sort(int[] arr) {
for(int i=0;i<arr.length;i++) { //每次冒泡固定的位置arr[i]
for(int j=arr.length-1;j>i;--j) {
if(arr[j] < arr[j-1]) { //每次總是交換相鄰元素
int temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
}
}
}
}
