算法学习-排序算法

秒速五厘米 2022-06-08 13:46 133阅读 0赞

# 排序算法 #

--------------------

## <table>   <thead>    <tr>     <th align="center">排序</th>     <th align="center">平均时间复杂度</th>    </tr>   </thead>   <tbody>    <tr>     <td align="center">冒泡排序</td>     <td align="center">O(n2)</td>    </tr>    <tr>     <td align="center">选择排序</td>     <td align="center">O(n2)</td>    </tr>    <tr>     <td align="center">插入排序</td>     <td align="center">O(n2)</td>    </tr>    <tr>     <td align="center">希尔排序</td>     <td align="center">O(n1.5)</td>    </tr>    <tr>     <td align="center">快速排序</td>     <td align="center">O(N*logN)</td>    </tr>    <tr>     <td align="center">归并排序</td>     <td align="center">O(N*logN)</td>    </tr>    <tr>     <td align="center">堆排序</td>     <td align="center">O(N*logN)</td>    </tr>    <tr>     <td align="center">基数排序</td>     <td align="center">O(d(n+r))</td>    </tr>   </tbody>  </table> ##

## **一.交换排序（冒泡排序、快速排序）** ##

### **1.冒泡排序（BubbleSort）** ###

**1. 基本思想：**

两个数比较大小，小的冒泡出来站前面;
    冒泡排序就是把小的元素往前调或者把大的元素往后调。

**2. 平均时间复杂度：** O(n2)、

序列{ 6, 5, 3, 1, 8, 7, 2, 4 }进行冒泡排序的实现过程

![这里写图片描述][SouthEast]

**3. java代码实现**

/**
         * 冒泡排序(BubbleSort) 
         * /
        public static void bubbleSort(int[] arr) {
            System.out.println(Arrays.toString(arr) + "<---原始数据");
            int temp;// 临时变量
            int time = 0;// 次数
            for (int i = 0; i < arr.length - 1; i++) {
       // 表示趟数，一共arr.length-1次。
                for (int j = arr.length - 1; j > i; j--) {
                    if (arr[j] < arr[j - 1]) {
                        temp = arr[j];
                        arr[j] = arr[j - 1];
                        arr[j - 1] = temp;
                        flag = true;
                    }
                    time++;
                    System.out.println(Arrays.toString(arr) + "<---第" + time + "遍结果");
                }
            }
            // 输出
            System.out.println(Arrays.toString(arr) + "<---排序后");
        }

**4. 优化：**

1. 针对问题：
            数据的顺序排好之后，冒泡算法仍然会继续进行下一轮的比较，直到arr.length-1次，后面的比较没有意义的。
     2. 方案：
          设置标志位flag，如果发生了交换flag设置为true；如果没有交换就设置为false。
        这样当一轮比较结束后如果flag仍为false，即：这一轮没有发生交换，说明数据的顺序已经排好，没有必要继续进行下去

**5. java代码实现**

/**
     * 冒泡排序(BubbleSort) 优化
     * /
    public static void bubbleSort(int[] arr) {
            System.out.println(Arrays.toString(arr) + "<---原始数据");
            int temp;// 临时变量
            int time = 0;// 次数
            boolean flag;
            for (int i = 0; i < arr.length - 1; i++) {
       // 表示趟数，一共arr.length-1次。
                flag = false;
                for (int j = arr.length - 1; j > i; j--) {
                    if (arr[j] < arr[j - 1]) {
                        temp = arr[j];
                        arr[j] = arr[j - 1];
                        arr[j - 1] = temp;
                        flag = true;
                    }
                    time++;
                    System.out.println(Arrays.toString(arr) + "<---第" + time + "遍结果");
                }
                if (!flag)
                    break;
            }
            // 输出
            System.out.println(Arrays.toString(arr) + "<---排序后");
        }

--------------------

### **2.快速排序(Quick Sort)** ###

**1. 思路 quickSort(arr\[\],left,right)**

1. 从数列中取一个数作为参照key=arr[left];挖出来作为key值，此时出现一个坑
     2. 从右边往左寻找，直到找到一个比key小的值，挖出来填到上一个坑中，
     3. 从左边往右寻找，直到找到一个比key大的值，挖出来填到上一个坑中，
     4. 坑分处了两个数列，继续2、3步，继续挖坑递归 。
     5.

**2. 平均时间复杂度：** O(N\*logN)

**3. java代码实现**

/** * 快速排序 * * @param arr * @param left * @param right */
        public static void quickSort(int[] arr, int left, int right) {
            System.out.println(Arrays.toString(arr));
            if (left >= right)
                return;
    
            int i = left;
            int j = right;
            int key = arr[left];//挖个坑
            while (i < j) {
    
                while (i < j && arr[j] >= key)// 从右往左 找比key小的值
                    j--;
                if (i < j) {
                    arr[i] = arr[j];//用比key小的值 填坑
                    i++;//数组下标后移
                }
    
                while (i < j && arr[i] < key)
                    i++;
    
                if (i < j) {
                    arr[j] = arr[i];//比key大的 填坑
                    j--;//数组下标前移
                }
            }
    
            if (i == j)
                arr[i] = key;
            quickSort(arr, left, i - 1);//坑前面的数列，继续挖坑
            quickSort(arr, i + 1, right);//坑后面的数列，继续挖坑
        }

--------------------

## **三 选择排序（直接选择排序、堆排序）** ##

### **1.直接选择排序（SelctionSort）** ###

**1. 基本思想**：

遍历找出最小的一个放在最前面

**2. 平均时间复杂度**：O(n2)

**3. java代码实现**

/** * 选择排序 */
        public static void selctionSort(int[] arr) {
            int temp;//临时变量
            for (int i = 0; i < arr.length - 1; i++) {
                int min = arr[i];
                for (int j = i; j < arr.length - 1; j++) {
                    if (arr[j + 1] < min) {
                        temp = min;
                        min = arr[j + 1];
                        arr[j + 1] = temp;
                    }
                    arr[i] = min;
                }
            }
        }

### **1.堆排序（HeapSort）** ###

**1. 基本思想**：

遍历找出最小的一个放在最前面

**2. 平均时间复杂度**：O(NlogN)

**3. java代码实现**

--------------------

[SouthEast]: /images/20220608/d4bb0f57842e4394b42d2fd268f10bd7.png