选择排序算法、时间复杂度和稳定

短命女 2022-05-17 06:15 98阅读 0赞

## 选择排序 ##

### 算法原理 ###

*  将数据分为有序部分和无序部分。
 *  在无序部分找出最大的元素，将最大的元素和无序部分最后一个元素交换，使得无序部分最后一个元素并入有序部分。
 *  重复第二步，直到无序部分都插入到有序部分结束。

### 算法分析 ###

排序的思想就是维护一个有序的部分，将无序部分中最大的元素和最后一个元素相交换，交换后无序部分的最后一个元素也将有序。

通俗的讲，选择排序的原理就是：

先从头遍历一遍找出最大元素，最大元素和最后一个元素相交换。

再从头遍历到倒数第二个元素找出最大元素，最大元素和倒数第二个元素相交换。

直到所有元素都有序为止。

### 代码实现 ###

/** * @Title: selectSort * @Description: 选择排序 * @param: array */
    public static void selectSort(int[] array) {
        int n = array.length;
        for (int i = 0; i < n; i++) {
            //记录最大元素的下标
            int max = 0;
            for (int j = 0; j<n-i; j++) {
                if (array[j] > array[max]) {
                    max = j;
                }
            }
            //最大元素和无序部分最后一个元素交换
            if (max != n-1-i) {
                swap(array, max, n-1-i);
            }
        }
    }
    
    /** * @Title: swap * @Description: 交换数组array中下标为i和j的元素 * @param: array * @param: i * @param: j */
    private static void swap(int[] array, int i, int j) {
        array[i] = array[i] + array[j];
        array[j] = array[i] - array[j];
        array[i] = array[i] - array[j];
    }

### 时间复杂度和算法稳定性 ###

从代码中可以看出一共遍历了n + n-1 + n-2 + … + 2 + 1 = n \* (n+1) / 2 = 0.5 \* n ^ 2 + 0.5 \* n，那么时间复杂度是O(N^2)。

因为在无序部分最大元素和有序部分第一个元素相等的时候，可以将无序部分最大元素放在前面，所以选择排序是稳定的。

## 相关代码都在github上:[https://github.com/LebronChenX/sort][https_github.com_LebronChenX_sort] ##

喜欢这篇文章的朋友，欢迎长按下图关注公众号**lebronchen**，第一时间收到更新内容。  
![扫码关注][70]

[https_github.com_LebronChenX_sort]: https://github.com/LebronChenX/sort
[70]: /images/20220517/9a1b6e05f57f4cfb88a013e036499d9f.png