五种排序算法-Java实现

五种排序算法-Java实现

排序算法在学习和面试扮演者十分重要的角色。对于排序算法，针对小规模的排序，熟练掌握插入排序算法，有余力的同学也可以看看插入排序的优化-希尔排序；针对大规模数据的排序，重点掌握快排算法。以下是五种算法的具体实现：

public class SortTest {
    public static void main(String[] args) {
        int[] nums = {1,23,44,0,-1,-99,999,-213,9922};
        for (int i : bubbleSort(nums)) {
            System.out.print(i+"->");
        }
        System.out.println();
        for (int i : insertSort(nums)) {
            System.out.print(i+"->");
        }
        System.out.println();
        for (int i : chooseSort(nums)) {
            System.out.print(i+"->");
        }
        System.out.println();
        for (int i : mergeSor(nums)) {
            System.out.print(i+"->");
        }
        System.out.println();
        for (int i : quickSort(nums)) {
            System.out.print(i+"->");
        }
    }


    
    public static int[] bubbleSort(int[] nums){
        if(nums == null || nums.length == 0){
            return null;
        }
        int len = nums.length;
        for (int i = 0; i  nums[j+1]){//如果前面的数字比后面的打--交换
                    int tmp = nums[j];
                    nums[j] = nums[j+1];
                    nums[j+1] = tmp;
                    noChanged= false;
                }
            }
            //未发生交换
            if(noChanged){
                break;
            }
        }
        return nums;
    }

    
    public static int[] insertSort(int[] nums){
        int len = nums.length;
        for (int i = 1; i  0 && nums[sortedLen] < element  ){
                sortedLen--;
           }
           //将待排序元素放入已排序区间确定位置
           nums[sortedLen] = element;
        }
        return nums;
    }

    
    public static int[] chooseSort(int[] nums){
        int len = nums.length;
        for (int i = 0; i < len; ++i) {
            //初始最小索引是已排序区间最大的数
            int minIndex = i;
            int j = i+1;
            //找到待排序区间的最小索引
            for (; j < len; ++j) {
                if(nums[j] < nums[minIndex]){
                    minIndex = j;
                }
            }
            //待排序区间的最小元素与已待排序区间的第一个元素交换位置
            int tmp = nums[i];
            nums[i] = nums[minIndex];
            nums[minIndex] = tmp;
        }
        return nums;
    }

    
    public static int[] mergeSor(int[] nums){
        int len = nums.length;
        int[] tmp = new int[len];
        sortByRecursion(nums,0,len-1,tmp);
        return nums;
    }

    private static void sortByRecursion(int[] nums, int left, int right, int[] tmp) {
        if(left < right){
            int middle = (left + right) / 2;
            sortByRecursion(nums,left,middle, tmp);
            sortByRecursion(nums,middle+1,right, tmp);
            sortByDetail(nums,left,middle,right,tmp);
        }
    }

    private static void sortByDetail(int[] nums, int left, int middle, int right, int[] tmp) {
        int leftBegin = left;
        int rightBegin = middle+1;
        int tmpIndex = 0;
        while (leftBegin <= middle && rightBegin <= right){
            if(nums[leftBegin] > nums[rightBegin]){
                tmp[tmpIndex++] = nums[rightBegin++];
            }else{
                tmp[tmpIndex++] = nums[leftBegin++];
            }
        }
        while (leftBegin <= middle){
            tmp[tmpIndex++] = nums[leftBegin++];
        }
        while (rightBegin <= right){
            tmp[tmpIndex++] = nums[rightBegin++];
        }
        //复制
        int initIndex = 0;
        while (left <= right){
            nums[left++] = tmp[initIndex++];
        }
    }

    
    public static int[] quickSort(int[] nums){
        int len = nums.length;
        quickSortByRecursion(nums,0,len-1);//这里是下标
        return nums;
    }

    private static void quickSortByRecursion(int[] nums, int left, int right) {
       if(left > right){
           return;
       }
       int pivot = nums[left];//基准数
       int leftBegin = left;
       int rightBegin = right;
       while (leftBegin < rightBegin){
           while (nums[rightBegin] >= pivot && leftBegin < rightBegin){
               //从右向左向前移动
               rightBegin--;
           }
           while (nums[leftBegin] <= pivot && leftBegin < rightBegin){
               //从左向右移动
               leftBegin++;
           }
           if(leftBegin < rightBegin){
               //交换位置
               int tmp = nums[leftBegin];
               nums[leftBegin] = nums[rightBegin];
               nums[rightBegin] = tmp;
           }
       }
       //确定基准数的位置后进行交换
        nums[left] = nums[leftBegin];
        nums[leftBegin] = pivot;
        quickSortByRecursion(nums,left,leftBegin-1);
        quickSortByRecursion(nums,rightBegin+1,right);
    }
}