基础排序算法（1）

你的名字 2022-05-18 03:38 128阅读 0赞

### 冒泡排序 ###

1、俩俩比较，大的放在后面，第一次排序后最大值已在数组末尾。

2、因为需要俩俩比较，需要n-1趟排序，比如10个数，需要9趟排序

3、两个for循环，外层循环控制排序的趟数，内层循环控制比较的次数，每趟过后，比较的次数都应该要减1

4、如果一趟排序后没有发生位置交换，说明已经有序，不需要继续循环了

/** * 冒泡排序 * * @author kaifeng */
    public class BubbleSort { 
    
        public static void main(String[] args) {
    
            //待排序数组
            int[] arrays = {
       1, 8, 9, 3, 5, 6};
    
            //是否排好序，默认值-1，正在排序
            int isChange = -1;
    
            //外层循环是排序的趟数
            for (int i = 0; i < arrays.length - 1; i++) {
    
                //每比较一趟就重新初始化为0
                isChange = 0;
    
                //内层循环是当前趟数需要比较的次数
                for (int j = 0; j < arrays.length - i - 1; j++) {
                    int temp = 0;
                    //前一位与后一位、比较，如果前一位比后一位要大，那么交换
                    if (arrays[j] > arrays[j + 1]) {
                        temp = arrays[j];
                        arrays[j] = arrays[j + 1];
                        arrays[j + 1] = temp;
                        //发生了位置交换
                        isChange = 1;
    
                    }
                }
                //如果比较完一趟没有发生置换，那么说明已经排好序了，不需要再执行下去了
                if (isChange == 0) {
                    break;
                }
    
            }
            System.out.println("冒泡排序结果：" + Arrays.toString(arrays));
        }
    
    }

### 选择排序 ###

找到数组中最大的元素，与数组最后一位元素交换，  
当只有一个数时，则不需要选择了，因此需要n-1趟排序，比如10个数，需要9趟排序

两个for循环，外层循环控制排序的趟数，内层循环找到当前趟数的最大值，随后与当前趟数组最后的一位元素交换

/** * 选择排序 * * @author kaifeng */
    public class SelectSort { 
        public static void main(String[] args) {
            //待排序数组
            int[] arrays = {
       1, 8, 9, 3, 5, 6};
            int pos = 0;
            //外层循环控制需要排序的趟数
            for (int i = 0; i < arrays.length - 1; i++) {
    
                int temp = 0;
                //新的趟数重新赋值为0
                pos = 0;
    
                //内层循环控制遍历数组的个数并得到最大数的下标
                for (int j = 0; j < arrays.length - i; j++) {
                    if (arrays[j] > arrays[pos]) {
                        pos = j;
                    }
                }
                //交换
                temp = arrays[pos];
                arrays[pos] = arrays[arrays.length - 1 - i];
                arrays[arrays.length - 1 - i] = temp;
    
            }
    
            System.out.println("选择排序结果：" + Arrays.toString(arrays));
        }
    }

### 插入排序 ###

将一个元素插入到已有序的数组中，在初始时未知是否存在有序的数据，因此将元素第一个元素看成是有序的  
与有序的数组进行比较，比它大则直接放入，比它小则移动数组元素的位置，找到个合适的位置插入  
当只有一个数时，则不需要插入了，因此需要n-1趟排序，比如10个数，需要9趟排序

一个for循环内嵌一个while循环实现，外层for循环控制需要排序的趟数，while循环找到合适的插入位置(并且插入的位置不能小于0)

/** * @author kaifeng */
    public class InsertSort { 
        public static void main(String[] args) {
    
            int[] arrays = {
       1, 8, 9, 3, 5, 6};
            //临时变量
            int temp;
    
            //外层循环控制需要排序的趟数,下标从1开始
            for (int i = 1; i < arrays.length; i++) {
                temp = arrays[i];
    
                //如果前一位数比当前大，则进入循环比较
                int j = i - 1;
    
                while (j >= 0 && arrays[j] > temp) {
    
                    //往后退一个位置，让当前数据与之前前位进行比较
                    arrays[j + 1] = arrays[j];
    
                    //不断往前，直到退出循环
                    j--;
    
                }
                //退出了循环说明找到了合适的位置了，将当前数据插入合适的位置中
                arrays[j + 1] = temp;
    
            }
            System.out.println("选择排序结果：" + Arrays.toString(arrays));
        }
    }

### 快速排序 ###

在数组中找一个元素，比它小的放在节点的左边，比它大的放在节点右边。一趟下来，比节点小的在左边，比节点大的在右边。

/** * 快速排序，使用递归实现 * * @author kaifeng */
    public class QuickSort { 
        public static void main(String[] args) {
            int[] arrays = {
       1, 8, 9, 3, 5, 6};
            quickSort(arrays, 0, arrays.length - 1);
            System.out.println(Arrays.toString(arrays));
        }
    
    
        /** * 快速排序 * * @param arr 待排序数组 * @param first 指向数组第一个元素 * @param end 指向数组最后一个元素 */
        public static void quickSort(int[] arr, int first, int end) {
            int i = first;
            int j = end;
    
            //中间点
            int pivot = arr[(first + end) / 2];
    
            //左右两端进行扫描，只要两端还没有交替，就一直扫描
            while (i <= j) {
    
                //寻找直到比中间点大的数
                while (pivot > arr[i]) {
                    i++;
                }
    
                //寻找直到比中间点小的数
                while (pivot < arr[j]) {
                    j--;
                }
    
                //此时已经分别找到了比中间点的数(右边)、比中间点的数(左边)，它们进行交换
                if (i <= j) {
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                    i++;
                    j--;
                }
            }
            //上面一个while保证了第一趟排序中间点的左边比中间点小，中间点的右边比中间点大了。
    
    
            //“左边”再做排序，直到左边剩下一个数(递归出口)
            if (first < j) {
                quickSort(arr, first, j);
            }
    
            //“右边”再做排序，直到右边剩下一个数(递归出口)
            if (i < end) {
                quickSort(arr, i, end);
            }
        }
    }