Java排序-冒泡排序、插入排序和选择排序

插入排序
1、特殊:从第二个元素开始,和第一个元素比较,如果满足排序的顺序,则交换顺序。
2、一般:把待比较和他之前的所有元素相比(从右往左),如果满足排序的顺序,这交换。

private static void insertSort(int[] arr){

        for (int i = 1; i < arr.length; i++){ //从第二个元素开始
            for (int j = i; j > 0; j--){ //这个元素和之前的元素比较
                if (arr[j] < arr[j-1]){
                    int temp = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = temp;
                }
            }
        }
}

2、冒泡排序
1、从第一个元素开始,和第二个元素相比,如果满足排序条件,则交换
2、把未排序的元素和后面的元素依次比较,如果满足排序条件,则交换

最初

private static void bubbleSort(int[] arr){

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

因为每次循环后,i前面的元素已经排好序。所以可以进行优化。
优化后:

private static void bubbleSort(int[] arr){

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

3、选择排序
1、从第一个位置开始遍历待排序的元素,找到最小值和第一元素交换
2、从位置i开始往后遍历,找到i之后元素中的最小值,和第i个元素交换位置。

private static void selectSort(int[] arr){

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

评论

暂无评论