Eight sorting algorithm practices

As for the sorting algorithm, it has not been used much in recent years. It is basically used and I have never taken the time to understand it in depth. Recently I decided to write it myself to deepen my understanding. I checked a lot of information, and many of them were analyzed very well, which helped me to understand quickly. Thank you!

1. Conceptual understanding and implementation

package com.demo.algorithm.sort;
/**
 * 排序算法合集
 * @author sheungxin
 *
 */
public class NumberSort {
/**
* 插入排序-直接插入排序
* 工作原理：构建有序序列，对于未排序的数据，在已排序序列中从后向前扫描，找到相应位置并插入
* 参考：http://blog.csdn.net/morewindows/article/details/6665714
* @param array
* @param asc 0:升序  1:降序
*/
public static void straightInsertSort(int[] array,int asc){
int tmp,n;
//从第二位元素开始，第一位认为已被排序
for(int m=1;m<array.length;m++){
tmp=array[m];
//在已排序序列中从后向前扫描,若该元素>(<)新元素，将该新元素向后移一位
for(n=m-1;n>=0&&(asc==1&&tmp>array[n]||asc==0&&tmp<array[n]);n--){
array[n+1]=array[n];
}
//上述循环在该元素<=(>=)新元素或者扫描到首位时结束,将该元素插入在结束位置后面
array[n+1]=tmp;
}
display(array);
}
/**
* 插入排序-希尔排序，实质就是分组排序，又称缩小增量排序
* 工作原理：先将整个待排序元素序列分割成若干个子序列(由相隔某个“增量”元素组成)分别进行直接插入排序，
*     然后依次缩减增量再进行排序，待整个序列中元素基本有序(增量足够小)时，再进行一次全元素直接插入排序。
* 优势：直接插入排序在元素基本有序的情况下，效率最高
* 参考：http://blog.csdn.net/morewindows/article/details/6668714
* @param array
* @param asc 0:升序  1:降序
*/
public static void shellSort(int[] array,int asc){
int len=array.length;
//依次缩减增量，直到增量为1
for(int gap=len/2;gap>0;gap/=2){
//根据步长把待排序元素分为gap组
for(int i=0;i<gap;i++){
//分别对每组元素进行直接插入排序，从i开始以增加gap得到一组元素
for(int j=i+gap;j<len;j+=gap){
int tmp=array[j];
int k=j-gap;//上一个节点
//在已排序序列中从后向前扫描,若该元素>(<)新元素，将该新元素向后移一位
while(k>=0&&(asc==1&&tmp>array[k]||asc==0&&tmp<array[k])){
array[k+gap]=array[k];
k-=gap;//向前扫描，移到下标
}
//上述循环在该元素<=(>=)新元素或者扫描到首位时结束,将该元素插入在结束位置后面
array[k+gap]=tmp;
}
}
}
   display(array);
}
/**
* 选择排序：简单选择排序
* 原理：从无序区中选择一个最小的元素之间放到有序区的最后
* 参考：http://blog.csdn.net/morewindows/article/details/6671824
* @param array
* @param asc 0:升序  1:降序
*/
public static void selectSort(int[] array,int asc){
int tmp,ix;
for(int i=0;i<array.length;i++){
ix=i;//最小或最大元素的位置
//从无序区中选择一个最小或最大的元素的位置
for(int j=i+1;j<array.length;j++){
if((asc==0&&array[ix]>array[j])||(asc==1&&array[ix]<array[j])){
ix=j;
}
}
//交换位置
if(ix!=i){
tmp=array[i];
array[i]=array[ix];
array[ix]=tmp;
}
}
display(array);
}
/**
* 选择排序：堆排序
* 原理：二叉堆近似二叉树，父节点总是大于或等于(小于或等于)任何一个子节点
* 参考：http://blog.csdn.net/morewindows/article/details/6709644
*    http://blog.csdn.net/kimylrong/article/details/17150475
* @param array
* @param asc 0:升序  1:降序
*/
public static void heapSort(int[] array,int asc){
//构建二叉堆，从最后一个父节点开始
for(int i=array.length/2-1;i>=0;i--){
buildHeap(array, array.length, i, asc);
}
//使用堆根节点构建有序序列
for(int i=array.length-1;i>=1;i--){
//依次把根节点向后交换构建有序序列
swapArray(array, 0, i);
//根节点交换位置后，从0，i-1重新构建堆
buildHeap(array, i, 0, asc);
}
display(array);
}
/**
* 构建二叉堆
* @param array 二叉堆数组
* @param heapSize 二叉堆大小
* @param index 当前父节点位置
* @param asc 0:升序  1:降序
*/
private static void buildHeap(int[] array,int heapSize,int index,int asc){
//比较父节点、左右叶子节点，找出最大或最小节点位置
int left = index * 2 + 1;  
        int right = index * 2 + 2; 
int ix=index;
if(left<heapSize&&(asc==1&&array[index]>array[left]||asc==0&&array[index]<array[left])){
ix=left;
}
if(right<heapSize&&(asc==1&&array[ix]>array[right]||asc==0&&array[ix]<array[right])){
ix=right;
}
if(ix!=index){
swapArray(array, index, ix);//交换父节点和叶子节点位置，满足最大/小堆性质
//递归向下交换，非最下层父节点与叶子节点交换会破坏下层最大/小堆性质
buildHeap(array, heapSize, ix, asc);
}
}
/**
* 交换排序：冒泡排序
* 参考: http://blog.csdn.net/morewindows/article/details/6657829
* @param array
* @param asc 0:升序  1:降序
*/
public static void bubbleSort(int[] array,int asc){
for(int i=0;i<array.length;i++){
for(int j=1;j<array.length-i;j++){
if((asc==0&&array[j-1]>array[j])||(asc==1&&array[j-1]<array[j])){
swapArray(array, j-1, j);
}
}
}
/**有点像交换排序、直接插入排序，交换次数过多
//从第二个元素开始依次与其左边元素进行比较
for(int m=1;m<array.length;m++){
//从左边最远的元素开始比较
for(int n=0;n<m;n++){
//满足条件交换位置
if((asc==0&&array[m]>array[n])
||(asc==1&&array[m]<array[n])){
swapArray(array, m, n);
}
}
}**/
display(array);
}
/**
* 交换排序：快速排序，在同为O(N*logN)的几种排序算法中效率较高，经常被使用
* 原理：从元素序列中取一个数作为基准数，左右分别放大于或小于的元素，再对左右区间重复上述操作，直到各区间只有一个数
* 参考: http://blog.csdn.net/morewindows/article/details/6684558
* @param array
* @param asc 0:升序  1:降序
*/
public static void quickSort(int[] array,int l,int r,int asc){
if(l<r){
int tmp=array[l];//把第一个节点作为基准数，视为第一个空位
int i=l;
int j=r;
//以基准数为标准，左右分别放大于或小于的节点
while(i<j){
//寻找右边小于(大于)基准数的节点位置
while(i<j&&(asc==0&&array[j]>=tmp||asc==1&&array[j]<=tmp)){
j--;
}
//把右边找到的节点放到左边的空位
array[i]=array[j];
//寻找右边大于(小于)基准数的节点位置
while(i<j&&(asc==0&&array[i]<=tmp||asc==1&&array[i]>=tmp)){
i++;
}
//把左边找到的节点放到右边的空位
array[j]=array[i];
}
//把基准数放在中间节点
array[i]=tmp;
//对中间点左边的元素重复上述操作
quickSort(array, l, i-1, asc);
//对中间点右边的元素重复上述操作
quickSort(array, i+1, r, asc);
}
display(array);
}
/**
* 归并排序：将两个(或两个以上)有序表合并成一个新的有序表
* 原理：将序列不断拆分，再反向两两合并形成有序序列
* 时间复杂度：O(nlogn)
* 参考：http://www.cnblogs.com/jingmoxukong/p/4308823.html
* @param array
* @param l 左指针
* @param r 右指针
* @param asc 0:升序  1:降序
*/
public static void mergeSort(int[] array,int l,int r,int asc){
//找出中间点，左右拆分为两个序列
int m=(l+r)/2;
if(l<r){
//左边序列，递归拆分直到间隔为0
mergeSort(array, l, m, asc);
//右边，递归拆分直到间隔为0
mergeSort(array, m+1, r, asc);
//左右归并
merge(array, l, m, r, asc);
}
display(array);
}
/**
* 左右归并为有序集合
* @param array
* @param l 左指针
* @param m 中间指针
* @param r 右指针
*/
private static void merge(int[] array,int l,int m,int r,int asc){
int[] tmp=new int[r-l+1];
int i=l;//左指针
int j=m+1;//右指针
int k=0;
//把较小的数先移到临时数组中
while(i<=m&&j<=r){
if(asc==0&&array[i]<array[j]||asc==1&&array[i]>array[j]){
tmp[k++]=array[i++];
}else{
tmp[k++]=array[j++];
}
}
//把左边剩余的数移到数组中
while(i<=m){
tmp[k++]=array[i++];
}
//把右边剩余的数移到数组中
while(j<=r){
tmp[k++]=array[j++];
}
//把临时数组中的数覆盖原数组，形成有序集合
for(k=0;k<tmp.length;k++){
array[l+k]=tmp[k];
}
}
/**
* 基数/桶排序：将序列分到有限数量的桶子里，再分别排序
* 原理：将序列分到有限数量的桶子里，再分别排序
* 时间复杂度：O(nlog(r)m)，r为所采用的基数，m为堆数
* 参考：http://www.cnblogs.com/jingmoxukong/p/4308823.html
* @param array
* @param l 左指针
* @param r 右指针
* @param asc 0:升序  1:降序
*/
public static void radixSort(int[] array,int digit,int asc){
final int radix=10;//基数，阿拉伯数字0~9，视为10个桶
int i=0;
int j=0;
int[] count=new int[radix];//存放各个桶存放数据的个数
int[] tmp=new int[array.length];
//按照从低到高位进行排序
for(int d=1;d<=digit;d++){
//置空各个桶的统计数据
for(i=0;i<radix;i++){
count[i]=0;
}
//根据位数d，统计各个桶存放数据的个数
for(i=0;i<array.length;i++){
j=array[i]/((Double)Math.pow(10, d-1)).intValue()%10;//d位上的数据
count[j]++;
}
//把count[i]的值由存放的个数改变了有边界的索引
for(i=1;i<radix;i++){
count[i]+=count[i-1];
}
//将数据依次装入临时桶里，从右向左扫描
for(i=array.length-1;i>=0;i--){
j=array[i]/((Double)Math.pow(10, d-1)).intValue()%10;//d位上的数据
tmp[count[j]-1]=array[i];//count[j]-1为第J个桶右边界的下标
count[j]--;//桶j装入数据索引减1
}
//按照桶中数据顺序放入原数据序列中
for(i=0;i<array.length;i++){
if(d==digit){
if(asc==0){
array[i]=tmp[i];
}else{
array[i]=tmp[array.length-i-1];
}
}else{
array[i]=tmp[i];
}
}
}
display(array);
}
/**
* 数组中指定位置的值交换位置
* @param array
* @param i
* @param j
*/
private static void swapArray(int[] array,int i,int j){
array[i]=array[j]^array[i];
array[j]=array[i]^array[j];
array[i]=array[i]^array[j];
}
/**
* 输出数组
* @param array
*/
private static void display(int[] array){
StringBuilder builder=new StringBuilder("[");
for(int i=0;i<array.length;i++){
builder.append(array[i]);
if(i<array.length-1){
builder.append(",");
}else{
builder.append("]");
}
}
System.out.println(builder.toString());
}
public static void main(String[] args) {
int[] array=new int[]{11,56,35,62,97,21,36,33,86,81,35};
//straightInsertSort(array, 0);
//shellSort(array, 0);
//selectSort(array, 0);
//heapSort(array, 0);
//bubbleSort(array,0);
//quickSort(array, 0, array.length-1, 0);
//mergeSort(array, 0, array.length-1,1);
radixSort(array, 3, 0);
}
}

2. Sorting algorithm comparison chart

Quote

http://blog.csdn.net/hguisu/article/details/7776068

3. Selection sorting algorithm guidelines

There are many factors that affect sorting, and the algorithm with low average time complexity is not necessarily the optimal one. Conversely, sometimes an algorithm with a high average time complexity may be more suitable for some special cases. At the same time, when selecting an algorithm, its readability must also be considered to facilitate software maintenance. Generally speaking, the following four factors need to be considered:
1), the size of the number n of records to be sorted;
2), the size of the data volume of the record itself, that is, the amount of other information in the record except keywords Size;
3), keyword structure and distribution;
4), requirements for sorting stability.

Suppose the number of elements to be sorted is n.
1) When n is large, a sorting method with a time complexity of O(nlog2n) should be used: quick sort, heap sort or merge sort.
a. Quick sort: It is currently considered the best method among internal sorting based on comparison. When the keywords to be sorted are randomly distributed, the average time of quick sort is the shortest;
b. Heap sort: If the memory space allows And require stability;
c. Merge sort: It has a certain amount of data movement, so we may combine it with insertion sort to first obtain a sequence of a certain length and then merge it, which will improve the efficiency.
2), when n is large, memory space allows, and stability is required => Merge sort
3), when n is small, direct insertion or direct selection sort can be used.
a. Direct insertion sort: When the elements are distributed in order, direct insertion sort will greatly reduce the number of comparisons and the number of moving records;
b. Direct selection sort: The elements are distributed in order. If stability is not required, choose direct selection sort
4) Traditional bubble sorting is generally not used or not used directly.
5) Radix sort: It is a stable sorting algorithm, but it has certain limitations:
a. Keywords can be decomposed;
b. The recorded keywords have fewer digits, and it is better if they are dense;
c . If it is a number, it is best to be unsigned, otherwise the corresponding mapping complexity will be increased. You can sort the positive and negative values ​​separately first.

Quote

http://blog.csdn.net/hguisu/article/details/7776068