亲宝软件园·资讯

展开

简单选择排序(Simple Selection Sort)

Acx7 人气:0

介绍:

  简单选择排序的工作方式突出"选择"二字,每次从待排序数据中选择符合条件的元素放在已排序元素末尾。对于少量元素的排序,简单选择排序是一个有效的算法。

思想:

  第一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后再从剩余的未排序元素中寻找到最小(大)元素,然后放到已排序的序列的末尾。以此类推,直到全部待排序的数据元素的个数为零。

性能分析:

  时间复杂度:O(N^2)

  空间复杂度:O(1)

  稳定性:不稳定

代码实现:

// Java代码
class SimpleSelectionSort {
    public static void selectionSort(int[] a) {
        for (int i = 0; i < a.length - 1; i++) {// 遍历序列
            int minIndex = i;// 记录最小元素位置
            // 遍历无序序列寻找最小元素
            for (int j = i + 1; j < a.length; j++) {
                if (a[j] < a[minIndex]) {// 更新最小元素下标
                    minIndex = j;
                }
            }
            // 将最小值放到已排序序列的末尾
            int temp = a[i];
            a[i] = a[minIndex];
            a[minIndex] = temp;
        }
    }
}
// C++代码
class SimpleSelectionSort {
public:
    static void selectionSort(int a[], int length) {
        for (int i = 0; i < length - 1; i++) {// 遍历序列
            int minIndex = i;// 记录最小元素位置
            // 遍历无序序列寻找最小元素
            for (int j = i + 1; j < length; j++) {
                if (a[j] < a[minIndex]) {// 更新最小元素下标
                    minIndex = j;
                }
            }
            // 将最小值放到已排序序列的末尾
            int temp = a[i];
            a[i] = a[minIndex];
            a[minIndex] = temp;
        }
    }
};

算法优化:

  上面代码一次遍历只是找出未排序序列中的最小值,其实我们可以在遍历过程中同时找出最小值和最大值,并把每次找出的最大值按顺序放到每次排列数据的末尾。时间复杂度还是 O(N^2) ,只相对前面的减少了一半遍历次数。

// Java代码
class SimpleSelectionSort {
    public static void selectionSort(int[] a) {
        int left = 0;// 标记未排序序列左边界
        int right = a.length - 1;// 标记未排序序列右边界
        
        while (left < right) {// 遍历未排序序列
            int minIndex = left;// 记录最小元素位置
            int maxIndex = left;// 记录最大元素位置
            
            // 遍历无序序列寻找最小元素
            for (int i = left + 1; i <= right; ++i) {
                if (a[i] < a[minIndex]) {// 更新最小元素下标
                    minIndex = i;
                }
                if (a[i] > a[maxIndex]) {// 更新最大元素下标
                    maxIndex = i;
                }
            }
            // 将最小值放到已排序序列的左末尾
            int temp = a[left];
            a[left] = a[minIndex];
            a[minIndex] = temp;
            
            if (maxIndex == left) {// 处理最大值为a[left]的特殊情况
                maxIndex = minIndex;
            }
            
            // 将最大小值放到已排序序列的右末尾
            temp = a[right];
            a[right] = a[maxIndex];
            a[maxIndex] = temp;

            ++left;// 修改未排序序列范围
            --right;
        }
    }
}
// C++代码
class SimpleSelectionSort {
public:
    static void selectionSort(int a[], int length) {
        int left = 0;// 标记未排序序列左边界
        int right = length - 1;// 标记未排序序列右边界
        
        while (left < right) {// 遍历未排序序列
            int minIndex = left;// 记录最小元素位置
            int maxIndex = left;// 记录最大元素位置
            
            // 遍历无序序列寻找最小元素
            for (int i = left + 1; i <= right; ++i) {
                if (a[i] < a[minIndex]) {// 更新最小元素下标
                    minIndex = i;
                }
                if (a[i] > a[maxIndex]) {// 更新最大元素下标
                    maxIndex = i;
                }
            }
            // 将最小值放到已排序序列的左末尾
            int temp = a[left];
            a[left] = a[minIndex];
            a[minIndex] = temp;
            
            if (maxIndex == left) {// 处理最大值为a[left]的特殊情况
                maxIndex = minIndex;
            }
            
            // 将最大小值放到已排序序列的右末尾
            temp = a[right];
            a[right] = a[maxIndex];
            a[maxIndex] = temp;

            ++left;// 修改未排序序列范围
            --right;
        }
    }
};

 

加载全部内容

相关教程
猜你喜欢
用户评论