java面试重点-java基础常用排序算法(4种)

冒泡排序

写法:

public static void bubbleSort(int[] arr) {

    if (arr == null || arr.length < 2) {
        return;
    }

    for(int i = arr.length - 1; i > 0; i--) {
        for(int j = 0; j < i; j++) {
            if(arr[j] > arr[j + 1]) {
                swap(arr, j, j + 1);
            }
        }
    }

}

public static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

特点: 效率低，容易实现。

思想: 每一趟从待排序序列选择一个最小的元素放到已排好序序列的末尾，剩下的为待排序序列，重复上述步骤直到完成排序

选择排序

 @Test
    public void selectSort() {
        int[] arr = {1, 2, 3, 4, 55, 6, 67, 8, 88};

        // 总共要经过 N-1 轮比较
        for (int i = 0; i < arr.length - 1; i++) {
            int min = i;

            // 每轮需要比较的次数 N-i
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[min]) {
                    // 记录目前能找到的最小值元素的下标
                    min = j;
                }
            }

            // 将找到的最小值和i位置所在的值进行交换
            if (i != min) {
                int tmp = arr[i];
                arr[i] = arr[min];
                arr[min] = tmp;
            }

        }

        System.out.println(Arrays.toString(arr));


//输出结果为:1 2 3 4 6 8 55 67 88
    }

特点: 效率低，容易实现。

思想: 每一趟从待排序序列选择一个最小的元素放到已排好序序列的末尾，剩下的为待排序序列，重复上述步骤直到完成排序

插入排序

@Test
    public void insertionSort(){
        int[] arr = {1, 2, 3, 4, 55, 6, 67, 8, 88};

        int i,j,t=0;
        for (i = 1; i < arr.length; i++) {
            if (arr[i] < arr[i-1]){
                t=arr[i];
                for (j=i-1;j>=0 && t < arr[j]; j--){
                    arr[j+1] = arr[j];
                    //插入arr[i]
                    arr[j+1] = t;
                }
            }
        }

     System.out.println(Arrays.toString(arr));

//输出结果为:1 2 3 4 6 8 55 67 88 
    }

特点: 效率低，容易实现。

思想: 将数组分为两部分，将后部分元素逐一与前部分元素比较，如果前部分元素比 array[i]小，就将前部分元素往后移动。当没有比 array[i]小的元素，即是合理位置，在此位置插入 array[i]

快速排序

public class QuickSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        return quickSort(arr, 0, arr.length - 1);
    }

    private int[] quickSort(int[] arr, int left, int right) {
        if (left < right) {
            int partitionIndex = partition(arr, left, right);
            quickSort(arr, left, partitionIndex - 1);
            quickSort(arr, partitionIndex + 1, right);
        }
        return arr;
    }

    private int partition(int[] arr, int left, int right) {
        // 设定基准值（pivot）
        int pivot = left;
        int index = pivot + 1;
        for (int i = index; i <= right; i++) {
            if (arr[i] < arr[pivot]) {
                swap(arr, i, index);
                index++;
            }
        }
        swap(arr, pivot, index - 1);
        return index - 1;
    }

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

}

特点: 高效，时间复杂度为 nlogn。采用分治法的思想：首先设置一个轴值 pivot，然后以这个轴值为划分基准将待排序序列分成比 pivot 大和比 pivot 小的两部分，接下来对划分完的子序列进行快排直到子序列为一个元素为止。

内容整理自菜鸟教程
--https://www.runoob.com/w3cnote/ten-sorting-algorithm.html