常见排序算法实践

布满荆棘的人生 2022-09-23 08:14 22阅读 0赞

# 常见排序算法实践 #

## 介绍 ##

各种排序可能是很多公司面试时候会问的算法题，但是由于基础不扎实我们有一部分人可能没法当场写出代码实现。其实掌握些数据结构和算法知识对我们的成长是很有帮助的。常见的排序算法有，冒泡排序、选择排序和快速排序等。

### 冒泡排序 ###

冒泡排序的思想就是，每经过一轮(外循环)排序就可以得到最大/最小的值。
    从左至右相邻的两个元素比较排序。

**Code分析**

/**
     * 
     * 最差冒泡排序外循环n-1,内循环也是n-1。效率比较低<br>
     * 优化后的冒泡排序,内循环每次都可以减少一次。
     * 其要点就是每一次外循环就能沉淀出一个最小/最大的数。
     * 
     * @param data
     * @return
     */
    private static int[] bubbleSort(int[] data) {
    
        int len = data.length;
        // 外循环len-1次
        for (int i = 0; i < len - 1; i++) {
    
            //优化之前每次内循环len-1次(强烈不推荐)
            for (int j = 0; j < len - 1; j++) {
                if (data[j] > data[j + 1]) {
                    int tem = 0;
                    tem = data[j];
                    data[j] = data[j + 1];
                    data[j + 1] = tem;
                }
    
            }
    
            // 优化之后的算法
            for (int j = len - 1; j > 0; j--) {
                if (data[j - 1] > data[j]) {
                    int tem = 0;
                    tem = data[j - 1];
                    data[j - 1] = data[j];
                    data[j] = tem;
    
                }
            }
        }
        return data;
    }

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

**冒泡排序算法步骤拆解**

假如有4个数据 5,4,15,1
    
         第一次外循环 
             内循环3次
             第一次: 4、5、15、1 
             第二次: 4、5、15、1
             第三次: 4、5、1、15
    
         第二次外循环 
             内循环2次
             第一次:4、5、1、15 
             第二次:4、1、5、15 
    
         第三次外循环
             内循环1次
             第一次:1、4、5、15
    
         冒泡排序每一次外循环都可以沉淀下最小后最大的数。
         冒泡排序效率太低了,算法复杂度O(n*n)优化后可以达到一半的复杂度。
    
    
    备注:冒泡排序适合数据量小的排序，通常都不推荐使用。

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

### 简单选择排序法 ###

简单选择排序法的的要点就是，依次取元素和后面元素做大小比较，每一次外循环都可以取出一个最大/最小值。

**Code实现**

/**
     * 选择排序法
     * 
     * @param data
     * @return
     */
    private static int[] selectSort(int[] data) {
        int len = data.length;
        // 如果入参数组含有数据则开始排序
        for (int i = 0; i < len - 1; i++) {
            // len个数据,(len-1)个数据需要比较,最后一个当然不需要比较了。
            for (int j = (i + 1); j < len - 1; j++) {
                // 第n个数据,需要和len-n的数据比较。
                if (data[i] > data[j]) {
                    // 交换数据
                    int tem = 0;
                    tem = data[j];
                    data[j] = data[i];
                    data[i] = tem;
                }
            }
        }
    
        return data;
    }

**排序拆解步骤**

假如五个数: 
    
     第1个数要和后面4个数比较,小的占0下标 (第1次外循环)
     第2个数要和后面3个数比较,小的占1下标 (第2次外循环)
     第3个数要和后面2个数比较,小的占2下标 (第3次外循环)
     第4个数要和后面1个数比较,小的占3下标 (第4次外循环)
     第5个数就不需要比较了。
    
    
     假如有n个数: 
     第一个数要和后面(n-1)个数比较,小的占0下标
     第2个数要和后面(n-2)个数比较,小的占1下标 
     第3个数要和后面(n-3)个数比较,小的占2下标
     ...
    
     简单选择排序和冒泡排序都是思想比较简单的排序算法，实现也比较简单，但是效率却都比较低，因此实际应用并不多。接下来要介绍的快速排序法效率就比较高了，并且所使用的空间也不多。

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

### 快速排序法 ###

快速排序法的思想是采取了分治法来处理的，首先取一个基数作为参考标准。将数组中大于这个基数的放该基数的右边，
    将数组中小于这个基数的放到基数的左边，分完之后，再次对两边的同样走上面流程各自处理排序，
    直到最后都没法再分治了为止。

**Code代码实现**

/**
     * 快速排序算法
     * 
     * @param data
     * @param low
     * @param high
     * @return
     */
    private static int[] quickSort(int[] data, int low, int high) {
    
        if (low < high) {
    
            int middle = getMiddle(data, low, high); // 将list数组进行一分为二
    
            quickSort(data, low, middle - 1); // 对低字表进行递归排序
    
            quickSort(data, middle + 1, high); // 对高字表进行递归排序
    
        }
    
        return data;
    }
    
    
    /**
     * 获取中间值
     * 
     * @param data
     * @param low
     * @param high
     * @return
     */
    private static int getMiddle(int[] data, int low, int high) {
        int tmp = data[low];
        while (low < high) {
    
            while (low < high && data[high] >= tmp) {
                high--;
            }
    
            data[low] = data[high]; // 比中轴小的记录移到低端
            while (low < high && data[low] <= tmp) {
                low++;
            }
    
            data[high] = data[low]; // 比中轴大的记录移到高端
    
        }
    
        data[low] = tmp; // 中轴记录到尾
    
        return low; // 返回中轴的位置
    
    }

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

![快速排序示意图][y2dviOg.gif]

[y2dviOg.gif]: http://i.imgur.com/y2dviOg.gif