算法（一）常见排序

àì夳堔傛蜴生んèń 2022-11-14 13:14 157阅读 0赞

# 算法-常见排序 #

### 这里写目录标题 ###

*  算法-常见排序
 *   *  一. 常见排序列表
     *  二. 参考下马老师的快速排序记忆法
     *  三. 排序
     *   *  3.1 选择排序
         *  3.1.1 动图
         *  3.1.1 思路
         *  3.1.2 代码实现
         *  3.2 冒泡排序
         *  3.2.1 算法步骤
         *  3.2.2 动图
         *  3.2.3 代码
     *  3.3 插入排序
     *   *  3.3.1 算法步骤
         *  3.3.2 动图
         *  3.3.3 代码实现

## 一. 常见排序列表 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppbmlhbjIwMTY_size_16_color_FFFFFF_t_70_pic_center]

## 二. 参考下马老师的快速排序记忆法 ##

**选泡插，**  
**快归堆希统计基  
恩方恩老恩一三，  
对恩加k恩乘k，  
不稳稳稳不稳稳，  
不稳不稳稳稳稳。**

## 三. 排序 ##

### 3.1 选择排序 ###

### 3.1.1 动图 ###

![在这里插入图片描述][20210329173311154.gif_pic_center]

### 3.1.1 思路 ###

1.  定义最小数的位置 minPosition ，第一次排序的位置为0
2.  遍历找到最小数据的位置
3.  将最小数据的位置和**相对**第一个位置进行交换
4.  最外层加一个for循环

### 3.1.2 代码实现 ###

public class SelectionSort { 
    
        public static void main(String[] args) { 
            int[] array = { 1, 9, 5, 7, 8, 3, 2, 6, 4};
            selectionSort(array);
    
        }
    
        /** * 快速排序 */
        private static void selectionSort(int[] array) { 
            for (int j = 0; j < array.length-1; j++) { 
                int minPosition = j;
                for (int i = j; i < array.length; i++) { 
                    if (array[i] < array[minPosition]) { 
                        minPosition = i;
                    }
                }
                System.out.println("当前minPosition所在的位置：" + minPosition);
                swap(array, j, minPosition);
                print(array);
            }
        }
    
        /** * @param array * 打印 */
        private static void print(int[] array) { 
            System.out.print("排序后的位置为： ");
            for (int i = 0; i < array.length; i++) { 
                System.out.print("" + array[i] + " ");
            }
        }
    
        /** * @param array * @param i * @param j * i和j 位置交换 */
        private static void swap(int[] array, int i, int j) { 
            //将minPosition 挪到最前面
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    }

### 3.2 冒泡排序 ###

### 3.2.1 算法步骤 ###

1.  比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2.  对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3.  针对所有的元素重复以上的步骤，除了最后一个。
4.  持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

### 3.2.2 动图 ###

![在这里插入图片描述][20210329170449591.gif_pic_center]

### 3.2.3 代码 ###

public class BubbleSort { 
    
        public static void main(String[] args) { 
            int[] array = { 1, 9, 5, 7, 8, 3, 2, 6, 4};
            bubbleSort(array);
    
        }
    
        private static void bubbleSort(int[] array) { 
    
            for (int i = 0; i < array.length - 1; i++) { 
    
                for (int j = 0; j < array.length - i - 1; j++) { 
                    if (array[j] > array[j + 1]) { 
                        swap(array, j, j + 1);
                    }
                    print(array);
                }
            }
        }
        /** * @param array 打印 */
        private static void print(int[] array) { 
            System.out.print("\n排序后的位置为： ");
            for (int i = 0; i < array.length; i++) { 
                System.out.print("" + array[i] + " ");
            }
        }
    
        /** * @param array * @param i * @param j i和j 位置交换 */
        private static void swap(int[] array, int i, int j) { 
            //将minPosition 挪到最前面
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    
    }

## 3.3 插入排序 ##

### 3.3.1 算法步骤 ###

1.  将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
2.  从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

### 3.3.2 动图 ###

![在这里插入图片描述][20210330092256798.gif_pic_center]

### 3.3.3 代码实现 ###

public class InsertSort { 
    
        public static void main(String[] args) { 
            int[] array = { 1, 9, 5, 7, 8, 3, 9, 2, 6, 4};
            insertSort(array);
    
        }
    
        /** * 快速排序 */
        private static void insertSort(int[] array) { 
    
            for (int i = 0; i < array.length; i++) { 
                // 创建临时变量 储存需要插入的元素
                int temp = array[i];
                int j = i;
                //找到需要插入的位置
                while (j > 0 && temp < array[j - 1]) { 
                    array[j] = array[j - 1];
                    j--;
                }
                //将temp 插入
                if (i != j) { 
                    array[j] = temp;
                }
                print(array);
            }
        }
    
    
        /** * @param array 打印 */
        private static void print(int[] array) { 
            System.out.print("\n排序后的位置为： ");
            for (int i = 0; i < array.length; i++) { 
                System.out.print("" + array[i] + " ");
            }
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppbmlhbjIwMTY_size_16_color_FFFFFF_t_70_pic_center]: /images/20221022/7b44015c15314e0a899447d0e2dbae8f.png
[20210329173311154.gif_pic_center]: /images/20221022/3f3cbf1cd43048b7b4a2f6c1dfaeb310.png
[20210329170449591.gif_pic_center]: /images/20221022/fe8fc3c60efd4d669f32c9e024ef4d7a.png
[20210330092256798.gif_pic_center]: /images/20221022/fe45afcdc9034c98995bfbeb6c953769.png