常用O(n^2)排序算法总结【JAVA版】

1、插入排序

public void insertSort(int[] nums){
    	if(nums == null || nums.length<=0)
    		return;
    	
    	for(int i=1 ; i<nums.length ; i++){
    		int temp = nums[i];
    		
    		int j;
    		for(j=i ; j>0 && (nums[j-1] > temp) ; j--)
                    nums[j] = nums[j-1];

    		nums[j] = temp;
    	}
    }
           

2、选择排序

public int[] sortArray(int[] nums) {
        if(nums == null || nums.length <= 1){
            return nums;
        }

        for(int i=nums.length-1; i>=0; i--){
            int maxIndex = findMaxIndex(nums, 0, i+1);
            swap(nums, i, maxIndex);
        }
        return nums;
    }

    private int findMaxIndex(int[] nums, int i, int j){
        int max = nums[i];
        int maxIndex = i;

        for(int k=i; k<j; k++){
            if(nums[k] > max){
                max = nums[k];
                maxIndex = k;
            }
        }

        return maxIndex;
    }

    private void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
           

3、冒泡排序

public int[] sortArray(int[] nums) {
        if(nums == null || nums.length <= 1){
            return nums;
        }

        for(int i=nums.length-1; i>=0; i--){
            buble(nums, 0, i+1);
        }
        return nums;
    }

    private void buble(int[] nums, int i, int j){
        for(int k=i; k<j-1; k++){
            if(nums[k] > nums[k+1]){
                swap(nums, k, k+1);
            }
        }
    }

    private void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }