Java算法基础，详解几种经典排序

约定不等于承诺〃 2022-06-08 03:16 232阅读 0赞

选择排序

定义一个的标志位temp，默认为比较的第一个数的下标，分别与后面的数进行比较，若比比较的数字大，则把该数的下标赋给temp，循环一次结束后判断temp的值，若temp值跟第一个数的下标不一样，则把第一个数跟下标为temp的值交换，若temp值一样，则说明后面的数字都比第一个数大，则不交换，继续下一次循环，以此类推，直到循环结束，具体实现的代码如下：

public class Main {
    
        public static void main(String[] args) {
            int array[] = new int[]{2,4,6,8,1,3,5,7,10,9};
            int index,current;
            for(int i=0;i<array.length-1;i++){
                index=i;
                for(int j=i+1;j<array.length;j++){
                    if(array[index]>array[j]){
                        index = j;
                    }
                }
                if(index!=i){
                    current = array[i];
                    array[i] = array[index];
                    array[index] = current;
                }
            }
        }
    }

冒泡排序

冒泡排序，有一个口诀"大数沉底，小数往上飘"，可见，冒泡排序每一次找出的都是当前需要排列的数字中的最大的那个值，那样当所有的数都遍历过后，也就从小到大排好了序，具体实现如下：

public class Main {
    
        public static void main(String[] args) {
            int array[] = new int[]{2,4,6,8,1,3,5,7,10,9};
            int temp;
            for(int i=0;i<array.length;i++){
                for (int j=0;j<array.length-i-1;j++){
                    if(array[j]>array[j+1]){
                        temp = array[j];
                        array[j] = array[j+1];
                        array[j+1] = temp;
                    }
                }
            }
        }
    }

插入排序

插入排序，可以简单理解为在打扑克，每次拿到一张新的牌子都会对手中的牌子做比较，找到对应该牌的位置后插入，那样在手中的牌子则一直是排好序的。具体到数组中的话，把数组第一位数当作手中的牌，后面的数则是要插入的数字。具体代码实现如下：

public class Main {
    
        public static void main(String[] args) {
            int array[] = new int[]{2,4,6,8,1,3,5,7,10,9};
            int current,temp;
            //除去第一个数，后面均是要插入的数
            for(int i=1;i<array.length;i++){
                current = array[i]; //要插入的数
                temp = i; //记录插入数的位置
                for(int j=i-1;j>=0;j--){
                    if(array[j]>current){
                        array[j+1] = array[j];
                        temp --;
                    }
                }
                array[temp] = current;
            }
        }
    }

快速排序

快速排序采用了"二分"的思维。选用一个数作为基数（一般是数组中的第一个数），从右往左找小于基数的数i，从左到右找大于基数的数j，若i!=j，则交换两个数，若i==j，则退出当前循环，且array\[i\]与基数进行交换。这样通过基数就形成了两个区间，再重复以上操作，直到区间只剩下一个数字为止，最终实现小的数在基数的左边，大的数在基数的右边。具体实现代码如下：

public class Main {
    
        public static void main(String[] args) {
            int array[] = new int[]{2,4,6,8,1,3,5,7,10,9};
            quickSort(array,0,array.length-1);
            for (int i=0;i<array.length;i++){
                System.out.print(array[i]+" ");
            }
        }
    
        public static void quickSort(int[] array,int low,int high){
            if(low<high){
                int middle = sortUtil(array,low,high);
                //左边排序
                quickSort(array,low,middle-1);
                //右边排序
                quickSort(array,middle+1,high);
            }
        }
    
        public static int sortUtil(int[] array,int low,int high){
            int temp = array[low];
            while(low<high){
                //从右往左找到第一个比temp要小的值，交换
                while (low<high && array[high]>temp){
                    high--;
                }
                array[low] = array[high];
                //从左往右找到第一个比temp要大的值，交换
                while (low<high && array[low]<temp){
                    low++;
                }
                array[high] = array[low];
            }
            array[low] = temp;
            return low;
        }
    }

希尔排序

希尔排序沿用了插入排序的原理，同时也有"二分法"的思想在里面。先将要排序的一组数按某个增量d（n/2,n为要排序数的个数）分成若干组，每组中记录的下标相差d.对每组中全部元素进行直接插入排序，然后再用一个较小的增量（d/2）对它进行分组，在每组中再进行直接插入排序。当增量减到1时，进行直接插入排序后，排序完成。其中，以增量d一般为待排序的序列长度的一半。

public class Main {
    
        public static void main(String[] args) {
            int array[] = new int[]{2,4,6,8,1,3,5,7,10,9};
            int j,temp;
            for (int length=array.length/2; length>0; length/= 2) {
                for (int i=length; i<array.length; i++) {
                    temp=array[i];
                    for (j=i-length;j>= 0;j-=length) {
                        if (temp<array[j]) {
                            array[j+length]=array[j];
                        } else {
                            break;
                        }
                    }
                    array[j + length] = temp;
                }
            }
        }
    }

堆排序

堆排序的基本思想是将待排序的序列构造成一个大顶堆（从上往下，从左往右数字逐渐减小）。此时，整个序列的最大值就是堆顶的根节点。将它与堆数组的末尾元素交换，此时末尾元素就是最大值，然后将除去末尾元素的剩余的 n-1 个序列重新构造成一个堆，这样就会得到 n 个元素中次大的值。如此反复执行，便能得到一个有序序列了。

public class Main {
    
        public static void main(String[] args) {
            int array[] = {2,4,6,8,1,3,5,7,10,9};
            int i,temp;
            for (i = array.length / 2 - 1; i >= 0; i--) {
                // 构建一个大顶堆
                adjust(array, i, array.length - 1);
            }
            for (i = array.length - 1; i >= 0; i--) {
                // 将堆顶记录和当前未经排序子序列的最后一个记录交换
                temp = array[0];
                array[0] = array[i];
                array[i] = temp;
                // 将array中前i-1个记录重新调整为大顶堆
                adjust(array, 0, i - 1);
            }
        }
    
        public static void adjust(int[] array, int i, int len) {
            int temp,j;
            temp = array[i];
            for (j = 2 * i; j < len; j *= 2) {
                if (j < len && array[j] < array[j + 1]){
                    ++j;
                }
                if (temp >= array[j]){
                    break;
                }
                array[i] = array[j];
                i = j;
            }
            array[i] = temp;
        }
    }