[数据结构与算法]【八种排序算法】

八种排序算法

二分查找算法

三个参数：minIndex=0, centerIndex=(minIndex+maxIndex)/2, maxIndex=array.length-1

查找时，用中间索引的对应元素去比较，比较之后包含三种情况：

1. 要找的元素正好等于中间索引所对应的元素，那么返回中间索引，也就是说正好找到了；
2. 要找的元素小于中间索引所对应的元素，那么改变最大索引移动最大索引 maxlndex=centerlndex-1;;
3. 要找的的元素，比中间索引对应的元素要大,那么改变最小索引 minlndex= centerlndex+1;。

代码实现：

private static int getIndexByELE(int[] arr,int ele){
    //定义最小索引,中间索引,最大索引
	int minIndex=0;
    int maxIndex=arr.length-1;
    int centerIndex=(minIndex+maxIndex)/2;
    //如果说你要找的这个元素,正好等于中间索引所对应的元素,那么就返回中间索引
    while(minIndex <= maxIndex){
        if(ele == arr[centerIndex]){
            return centerIndex;
        }else if(ele > arr[centerIndex]){
            //如果你要找的元素大于中间索引所对应的元素,你就移动最小索引
            minIndex = centerIndex + 1;
        }else if(ele < arr[centerIndex]){
            //如果你要找的这个元素小于中间索引所对应的元素,你就移动最大索引
            maxIndex = centerIndex - 1;
        }
        //重新计算中间索引
        centerIndex =(minIndex + maxIndex)/2;
    } 
    return -1;//如果没有找到，就返回-1
}

1、冒泡排序

排序原理（由小到大）：数组元素两两比较，交换位置，大元素往后放，那么经过一轮比较后，最大的元素，就会出现在最大索引处。

• 需要进行length-1轮;
• 每排一轮可以确定一个数的位置

代码实现：

/**
 * int[] arr表示传入的数组,
 * flag为0表示由小到大，为1表示由大到小
 */
private static void bubbleSort(int[] arr,bool flag){
    //循环轮数
    for(int i=0; i<arr.length-1; i++){
        //每轮需要判断交换的次数
        for(int j=0; j<arr.length-1-i; j++){
            if(flag == 0){
                //由小到大排序
                if(arr[i] > arr[i+1]){
                    //交换位置
                    int t = arr[i];
                    arr[i] = arr[i+1];
                    arr[i+1] = t;
                } 
            }else{
                //由大到小排序
                if(arr[i] < arr[i+1]){
                    //交换位置
                    int t = arr[i];
                    arr[i] = arr[i+1];
                    arr[i+1] = t;
                } 
            }
             
        }
    }
}

2、选择排序

排序原理（由小到大）：从0索引处开始，依次和后面的元素进行比较，小的元素往前放，经过一轮比较后，最小的元素就出现在了最小索引处。

• 需要进行length-1轮;
• 每排一轮可以确定一个数的位置

代码实现：

/**
 * int[] arr表示传入的数组,
 * flag为0表示由小到大，为1表示由大到小
 */
private static void selectSort(int[] arr,bool flag){
    //循环轮数
    for(int index=0; index<arr.length-1; index++){
        //每轮需要判断交换的次数
        for(int i=index+1; i<arr.length; i++){
            if(flag == 0){
                //由小到大排序
                if(arr[index] > arr[i]){
                    //交换位置
                    int t = arr[index];
                    arr[index] = arr[i];
                    arr[i] = t;
                } 
            }else{
                //由大到小排序
                if(arr[index] < arr[i]){
                    //交换位置
                    int t = arr[index];
                    arr[index] = arr[i];
                    arr[i] = t;
                }  
            }  
        }
    }
}

3、插入排序

排序原理：直接插入排序，是一种最简单的排序方法，基本操作是将一个记录插入到一个长度为m的有序表中，使之仍保持有序。

• 从1索引处开始，将后面的元素，插入之前的有序列表中使之仍保持有序；
• 直接插入排序，等价于增量为1 的希尔排序。

代码实现：

/**
 * int[] arr表示传入的数组,
 * flag为0表示由小到大，为1表示由大到小
 */
private static void insertSort(int[] arr){
    //方法一
    //外层循环，定义轮数
    for(int i=1; i<arr.length; i++){
		//里层循环进行比较
        int j = i;
        while(j>0 && arr[j]<arr[j-1]){
            //由小到大排序
            //交换位置
            int t = arr[j];
            arr[j] = arr[j-1];
            arr[j-1] = t; 
            j--;
        }
    }
    //方法二
    /*
    for(int i=1; i<arr.length; i++){
		for(int j=i; j>0;j--){
            if(arr[j] < arr[j-1]){
                int t = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = t; 
            }
        }
    }
    */
}

4、希尔排序

希尔排序又称缩小增量排序，对插入排序的优化。
基本思想：先将原表按增量ht分组，每个子文件按照直接插入法排序。同样，用下一个增量ht/2将文件再分为子文件，再直接插入法排序。直到ht=1时整个文件排好序。
关键：选择合适的增量，经过一轮排序后会让序列大致有序，然后不断缩小增量，进行插入排序，直到增量为1。

• 可以通过三重循环来实现。
• 增量的选择，一般使用数组长度的一半（效率不太高），可使用Knuth序列（克努特序列，h = 3*h+1）

代码实现：

/**
 * int[] arr表示传入的数组
 */
private static void shellSort(int[] arr){
    int h = 1;
    while(h <= arr.length/3){
        h = 3*h+1;//由克努特序列得到适合的增量
    }
    //循环轮次
    for(h; h>0; h=(h-1)/3){
        //含有间隔的直接插入排序
        for(int i=h; i<arr.length; i++){
            for(int j=i; j>h-1; j-=h){
                if(arr[j] < arr[j-h]){
                    int t = arr[j];
                    arr[j] = arr[j-h];
                    arr[j-h] = t; 
                }
            }
    	}
    }   
}

5、快速排序

分治法：比大小，再分区

排序原理：

1. 从数组中取出一个数，作为基准数。
2. 分区：将比这个数大或等于的数全放到他的右边，小于他的数全放到他的左边。
3. 再对左右区间重复第二步，直到各区间只有一个数。

实现思路：（挖坑填数）

1. 将基准数挖出形成第一个坑。
2. 由后向前找比他小的数，找到后挖出此数填到前一个坑中。
3. 由前向后找比他大或等于的数，找到后也挖出此数填到前一个坑中。
4. 再重复执行2，3两步骤。

• 找出分左右两区的索引位置，然后对左右两区进行递归调用

代码实现：

//调用工具类的方法
QuickSortUtils.quickSort(arr,0,arr.length-1);

//方法实现
public class QuickSortUtils{
    //快速排序
    public static void quickSort(int[] arr, int start, int end){
        //找出分左右两区的索引位置，然后对左右两区进行递归调用
        if(start < end){
            int index = getIndex(arr,start,end);
            quickSort(arr,start,index-1);
            quickSort(arr,index+1,end);
        }
    }
    
    private static int getIndex(int[] arr, int start, int end){
        int i = start;
        int j = end;
        int x = arr[i];//基准数
        while(i < j){
            //由后向前找比他小的数，找到后挖出此数填到前一个坑中。
            while(i<j && arr[j]>=x){
                j--;
            }
            if(i<j){
                arr[i] = arr[j];
                i++;
            }
            //由前向后找比他大或等于的数，找到后也挖出此数填到前一个坑中。
                while(i<j && arr[i]<x){
                i++;
            }
            if(i<j){
                arr[j] = arr[i];
                j--;
            }
        }
        arr[i] = x;//把基准数填到最后一个坑中    
        return i;
    }
}

6、归并排序

排序原理：归并排序（Merge Sort）就是利用归并的思想实现排序的方法。
它的原理是假设初始序列有N个记录，则可以看成是N个有序的子序列，每个子序列的长度为1，然后两两归并，得到N/2个长度为2或1的有序子序列，再两两归并······，如此重复，直至得到一个长度为N的有序序列为止，这种排序方法称为2路归并排序。

• 分而治之，先拆后并

//拆分, 调用
split(arr,0,arr.length-1);

//归并
//mergeSort(arr,0,arr.length/2-1,arr.length);

private static void split(int[] arr, int startIndex, int endIndex){
    //计算中间索引
    int centerIndex = (startIndex+endIndex)/2;
    if(startIndex<endIndex){
        split(arr,startIndex,centerIndex);
        split(arr,centerIndex+1,endIndex);
        mergeSort(arr,startIndex,centerIndex,endIndex);
    }
    
}

private static void mergeSort(int[] arr, int startIndex, int centerIndex, int endIndex){
    //定义一个临时数组
    int[] tempArr = new int[endIndex - startIndex+1];
    //定义右边数组的起始索引
    int i = startIndex;
    //定义左边数组的起始索引
    int j = endIndex;
    //定义临时数组的起始索引
    int index = 0;
    //比较左右两个数组的元素大小，往临时数组中放
    while(i <= centerIndex && j <= endIndex){
        if(arr[i]<=arr[j]){
            tempArr[index] = arr[i];
            i++;
        }else{
            tempArr[index] = arr[j];
            j++;
        }
        index++;
    }
    //处理剩余元素
    while(i<=centerIndex){
        tempArr[index] = arr[i];
        i++;
        index++;
    }
    while(j<=endIndex){
        tempArr[index] = arr[j];
        j++;
        index++;
    }
    //将临时数组中的元素取到原数组中
    for(int k=0; k<tempArr.length; k++){
        arr[k+startIndex] = tempArr[k];
    }
}

7、基数排序

基数排序不同于之前所介绍的各类排序，前边介绍到的排序方法或多或少的是通过使用比较和移动记录来实现排序，

而基数排序的实现不需要进行对关键字的比较，只需要对关键字进行“分配"与“收集"两种操作即可完成。

• 先根据个位数分配 收集，再根据十位数分配 收集，依此类推

代码实现:

//调用方法
radixSort(arr);

//基数排序
private static void sortArray(int[] arr){
    //定义二维数组，放10个桶
    int[][] tempArr = new int[10][arr.length];
    //定义统计数组
    int[] counts = new int[10];
    //由数组最大值确定排序轮次
    int max = getMax(arr);
    int len = String.valueOf(max).length;
    //循环
    for(int i=0, n=1; i<len; i++, n*=10){
        for(int j=0; j<arr.length; j++){
            //获取每个位上的数字
            int num = arr[j]/n%10;
            tempArr[num][counts[num]++] = arr[j];
        }
        //取出桶中的元素
        int index = 0;
        for(int k = 0; k < counts.length; k++){
            if(counts[k] != 0 ){
                for(int h = 0; h < counts[k]; h++){
                    //从桶中取出元素放回原数组
                    arr[index] = tempArr[k][h];
                    index++;
                }
                counts[k] = 0;//清除上一次统计的个数
            }
        }
        
        
    }
}

private static int getMax(int[] arr){
    int max = arr[0];
    for(int i=1; i<arr.length; i++){
        if(arr[i]>max){
            max = arr[i];
        }
    }
    return max;
}

8、堆排序

堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序。

堆排序的基本思想：（升序排列使用大顶堆，降序排列使用小顶堆）

1. 将待排序序列构造成一个大顶堆（父节点的值大于两个子结点的值），此时，整个序列的最大值就是堆顶的根结点。
2. 将其与末尾元素进行交换，此时末尾就为最大值。
3. 然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。
4. 如此反复执行，便能得到一个有序序列了。

• 大顶堆：arr[i]>=arr[2i+1]&&arr[i]>=arr[2i+2]
• 小顶堆：arr[i<=arr[2i+1]&&arr[i]<=arr[2i+2]

步骤：数组–>完全二叉树–>大顶堆（从最后一个非叶子结点开始转，再到上一个非叶子结点）–>把根结点的元素跟最后一个元素进行调换

代码实现：

//调用
heapSort(arr);

//堆排序
/**
 * arr 要排序的数组
 *
 */
private static void heapSort(int[] arr){
    //调整成大顶堆的方法
    //定义开始调整的位置
    int startIndex = (arr.length-1)/2;
    //循环开始调
    for(int i = startIndex, i >= 0; i--){
        toMaxHeap(arr,arr.length,i);
    }
    //经过上面的操作后，已经把数组变成一个大顶堆，把根元素和最后一个元素进行调换
    for(int i = arr.length-1;i>0; i--){
        //进行调换
        int t = arr[0];
        arr[0] = arr[i];
        arr[i] = t;
        //换完之后，再把剩余元素调整大顶堆
        toMaxHeap(arr,i,0);
    }
    System.out.println(Arrays.toString(arr));//打印排序后的数组
}
//数组转换成大顶堆
/**
 * arr 要排序的数组
 * size 调整的元素个数
 * index 从哪里开始调整
 */
private static toMaxHeap(int[] arr,int size, int index){
    //获取左右字节的索引
    int leftNodeIndex = index*2+1;
    int rightNodeIndex = index*2+2;
    //查找最大结点所对应的索引
    int maxIndex = index;
    if(rightNodeIndex<size && arr[rightNodeIndex]>arr[maxIndex]){
        maxIndex = rightNodeIndex;
    }
    if(leftNodeIndex<size && arr[leftNodeIndex]>arr[maxIndex]){
        maxIndex = leftNodeIndex;
    }
    
    //调换位置
    if(maxIndex!=index){
        int t = arr[maxIndex];
        arr[maxIndex] = arr[index];
        arr[index] = t;
        //调换完之后，可能会影响到下面的子树（并不是大顶堆，还需要再次调换）
        toMaxHeap(arr,size,maxIndex);
    }
}

八大排序算法性能比较

资料整理来源：西部开源Java之数组与排序_哔哩哔哩_bilibili