文章目录

• 初级排序算法
• 选择排序
• 插入排序
• 希尔排序
• 冒泡排序
• 高级排序算法
• 归并排序
• 快速排序

初级排序算法

选择排序

• 动画演示
  

• 代码实现

public class selectSort {
    public static void main(String[] args) {
        int[] nums = {1,5,6,2,3,4,7,8,9};
        selectSort(nums);
        for (int num:nums){
            System.out.print(num);
        }
    }

    private static void selectSort(int[] nums){
        for (int i = 0;i<nums.length;i++){
            int minIndex = i;
            for (int j = i+1;j<nums.length;j++){
                if(nums[minIndex]>nums[j]){
                    minIndex = j;
                }
            }
            swap(nums,i,minIndex);
        }
    }

     private static void swap(int[] nums,int index1,int index2){
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}

插入排序

• 动画演示
  
• 代码实现

public class insertSort {
    public static void main(String[] args) {
        int[] nums = {1,5,6,2,3,4,7,8,9};
        insertSort(nums);
        for (int num:nums){
            System.out.print(num);
        }
    }

    private static void insertSort(int[] nums){
        int len = nums.length;
        for(int i = 1;i<len;i++){
            for(int j=i;j>0;j--){
                if(nums[j-1]>nums[j]){
                    swap(nums,j-1,j);
                }else{
                    break;
                }
            }
        }
    }

    private static void swap(int[] nums,int index1,int index2){
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}

• 优化版本

void insertSort1(int[] nums){
       int len = nums.length;
       for(int i = 1;i<len;i++){
           int temp = nums[i];
           int j = i-1;
           while (j>=0 && nums[j]>temp){
               nums[j+1] = nums[j];
               j--;
           }
           nums[j+1] = temp;
       }
   }

希尔排序

• 动画演示
  

• 代码实现

public class ShellSort {
    public static void main(String[] args) {
        int[] nums = {1,5,6,2,3,4,7,8,9};
        shellSort(nums);
        for (int num:nums){
            System.out.print(num);
        }
    }

    private static void shellSort(int[] nums){
        int len = nums.length;
        int dalta = len/2;
        while (dalta>=1){
            for(int i = len-1;i>=len-dalta;i--){
                for(int j = i;j>=dalta;j-=dalta){
                    if(nums[j-dalta]>nums[j]){
                        swap(nums,j-dalta,j);
                    }
                }
            }
            dalta /=2;
        }
    }

    private static void swap(int[] nums,int index1,int index2){
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }

}

冒泡排序

• 动画演示
  
• 代码实现

public class bubbleSort {
    public static void main(String[] args) {
        int[] nums = {1,5,6,2,3,4,7,8,9};
        bubbleSort(nums);
        for (int num:nums){
            System.out.print(num);
        }
    }

    private static void bubbleSort(int[] nums){
        int len = nums.length;
        for(int i = 0;i<len;i++){
            boolean flag = true;
            for (int j = 0;j<len-i-1;j++){
                if(nums[j]> nums[j+1]){
                    swap(nums,j+1,j);
                    flag = false;
                }
            }
            if(flag) break;
        }
    }

    private static void swap(int[] nums,int index1,int index2){
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}

高级排序算法

归并排序

• 动画演示
  
• 代码实现

public class megerSort {
    public static void main(String[] args) {
        int arr[] = { 8, 4, 5, 7, 1, 3, 6, 2, 9 };

        int temp[] = new int[arr.length]; //归并排序需要一个额外空间
        mergeSort(arr, 0, arr.length - 1, temp);

        System.out.println("归并排序后=" + Arrays.toString(arr));
    }

    private static void mergeSort(int[] arr, int left, int right, int[] temp) {
        if(left>=right){
            return;
        }

        int mid = left + (right-left)/2;
        //向左边递归分解
        mergeSort(arr,left,mid,temp);
        //向右边递归分解
        mergeSort(arr,mid+1,right,temp);
        //合并
        merge(arr,left,mid,right,temp);
    }

    private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left;
        int j = mid + 1;
        int t = 0;
        while (i<=mid && j<=right){
            if(arr[i]<=arr[j]){
                temp[t] = arr[i];
                t++;
                i++;
            }else{
                temp[t] = arr[j];
                t++;
                j++;
            }
        }

        while (i<=mid){
            temp[t] = arr[i];
            t++;
            i++;
        }
        while (j<=right){
            temp[t] = arr[j];
            t++;
            j++;
        }


        t = 0;
        int tempLeft = left;
        while (tempLeft<=right){
            arr[tempLeft] = temp[t];
            tempLeft++;
            t++;
        }
    }
}

快速排序

• 动画演示
  

• 代码实现

public class quickSort {
    public static void main(String[] args) {
        int[] nums = {1,5,2,6,4,7,8,9,-1,-2};
        quickSort(nums,0,nums.length-1);
        System.out.println(Arrays.toString(nums));
    }
    private static void quickSort(int[] nums,int left,int right){
        int l = left;
        int r = right;
        int mid = left + (right-left)/2;
        int privot = nums[mid];
        while (l<r){
            while (nums[l]<privot){
                l++;
            }
            while (nums[r]>privot){
                r--;
            }
            if(l>=r){
                break;
            }
            swap(nums,l,r);
            if (nums[l]==privot){
                r--;
            }
            if(nums[r]==privot){
                l++;
            }
        }
        if(l==r){
            l++;
            r--;
        }
        if (left<r){
            quickSort(nums,left,r);
        }
        if (right>l){
            quickSort(nums,l,right);
        }
    }

    private static void swap(int[] nums,int index1,int index2){
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}

注：本文的动画来源于网络。

你知道的越多，你不知道的越多。
有道无术，术尚可求，有术无道，止于术。
如有其它问题，欢迎大家留言，我们一起讨论，一起学习，一起进步