几个算法中使用的一个交换函数,源码如下,
//swap element at i to at j
private static void swap(int[] array, int i,int j){
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
以下7种排序算法都实现了序列的非降序排列,函数参数代表的含义一般统一定义为:
03
—
冒泡排序
//bubble sort
public static void bubbleSort(int[] array, int n){
int i = 0;// loop
int j = 0; // element index
while(i < n) {
for(j=0; j
if( array[j] > array[j+1] ){ //swap condition
swap( array, j, j +1 );
}
}
i++;
}
}
04
—
快速排序
快速排序是很巧妙的实现算法,它选取一个轴点,每轮计算时,凡是轴点的移动都会空出一个位置,这个位置就是被调整后的关键码所代替,经过这种调整后,一轮下来轴点前的关键码都小于轴点,后的都大于。
注意 里层的两个while遍历条件,最后碰头的位置,就是这轮轴点的位置,记得给这个填上轴点值。
//quick sort
public static void quickSort(int[] array, int lo, int hi){
if(lo>hi) return;
int pivot = array[lo];
int i = lo;
int j = hi;
while( i<j ){
//get smaller after pivot
//warning: while condition, here and next while
//at least one item is >=
while(i < j && array[j] >= pivot){
j--;
}
array[i] = array[j]; //so at j an element is void
//get bigger before pivot
while(i < j && array[i] < pivot){
i++;
}
array[j] = array[i]; // at i an element is to fill at j
}
//here, i bumps into j
array[i] = pivot;
//here, before index i smaller than pivot, after bigger than pivot
// lo~i quick sort
quickSort(array, lo, i-1);
// i+1~hi quick sort
quickSort(array, i+1, hi);
}
05
—
直接选择排序
直接选择排序就是把每轮找出的最小值放到排序区的最后,代码实现简单。
//direct select sort
public static void selectSort(int[] array, int n){
int i=0; //sorted last element
int j=0; //unsorted first element
while(i<n){
int min=array[i];
int index = i;
for(j=i+1; j<n;j++){
if(array[j]<min){
min = array[j];
index = j;
}
}
swap(array,i,index);
i++;
}
}
06
—
堆排序
注意大根堆顶与未排序区的最后一个元素不断交换,直至未排序区的个数为0,整个序列完成排序。
堆排序算法比较容易出错的点:
//heap sort
public static void heapSort(int[] array, int n){
for (int i = n / 2 - 1; i >= 0; i--)
buildHeap(array, n, i);
int len = n - 1;
while (len > 0) {
swap(array, 0, len);
buildHeap(array, len, 0);
len--;
}
}
private static void buildHeap(int[] array, int n, int i){
for (; left(i) < n; i = left(i)) {
int bigger =
right(i) < n ? max(array, left(i), right(i)) : left(i);
if (array[bigger] > array[i]) //swap
swap(array, bigger, i);
else break;
}
}
private static int left(int i){
return 2*i+1;
}
private static int right(int i){
return 2*i+2;
}
private static int max(int[] array, int i, int j){
return array[i]>array[j]? i:j;
}
07
—
直接插入排序
插入排序算法,需要注意在移动排序区的元素时,会覆盖未排序区的第一个元素,所以需要先用另一个变量标记出来。
// insert sort
public static void insertSort(int[] array, int n){
int i = 1; //unsorted first index
while (i < n) {
int j = i - 1; //sorted last index
int insert = array[i]; //warning: label array[i]
while (j > 0 && insert < array[j]){
array[j + 1] = array[j];
j--;
}
array[j + 1] = insert; //j+1 is insert pos
i++;
}
}
08
—
希尔排序
希尔排序的精华是在插入排序的思想下多了一层分组逻辑,如下所示,d为分组长度,k为分组索引。内层逻辑实际上为插入排序的逻辑。
//shell Sort
public static void shellSort(int[] array, int n, int group){
if (group > n) return;
int d = n / group; //d: number for each group
while (d > 0){
for (int i = 0; i < d; i++){
int j = i; // number index
int k = 1; //distance index
while (j < n){
int insert = array[j]; //label unsorted first
j -= d; //sorted last index
while (j > 0 && insert < array[j]){
array[j + d] = array[j];
j -= d;
}
array[j + d] = insert; //insert pos: j+d
j = i + (++k) * d; //next number index
}
}
d /= 2;
}
}
09
—
归并排序
二分后再归并是这个算法的精华所在,需要注意的是,递归排序的前半部分和后半部分各自的起始终止索引,以及归并时要分别指出array被分隔的两半部分的起始,终止位置,当然划分的前提是lo < hi,这也是递归返回的条件。
//merge sort
public static void mergeSort(int[] array, int n){
var sorted = new int[n];
mergeSort(array,sorted,0,n-1);
}
private static void mergeSort(int[] array, int[] sorted, int lo, int hi){
if (lo < hi){
int mid = lo + (hi - lo) / 2;
mergeSort(array, sorted,lo, mid);
mergeSort(array, sorted, mid + 1, hi);
merge(array, sorted, lo, mid, hi);
}
}
//beg: part1 beginning index
//mid: part1 end index
//mid+1: part2 beginning index
//end: part2 end index
private static void merge(int[] array, int[] sorted, int beg, int mid, int end){
int i = beg; //part1 index
int j = mid + 1; //part2 index
int k = 0; //merged index
while (i <= mid && j <= end)
sorted[k++] =
array[i] <= array[j] ? array[i++] : array[j++];
while (i <= mid)
sorted[k++] = array[i++];
while (j <= end)
sorted[k++] = array[j++];
for (i = 0; i < k; i++)
array[beg + i] = sorted[i];
}
10
—
总结
对以上算法不清晰的地方请直接参考以下推送:
冒泡排序到快速排序做的那些优化
直接选择排序到堆排序做的那些改进
直接插入排序到希尔排序做的那些改进
归并排序算法的过程图解
不基于比较的基数排序原理图解
来源: https://mp.weixin.qq.com/s?__biz=MzI3NTkyMjA4NA==&mid=2247483808&idx=1&sn=9d90856f16a20b4a1846eb1680334a4e&chksm=eb7c2c6bdc0ba57dfeb93f78b65952019f12e6371b763bb73f343485c1549e45c8173778ee5a#rd