【LintCode】463.整数排序-各种排序解析

描述

中文English

给一组整数，按照升序排序，使用选择排序，冒泡排序，插入排序或者任何 O(n2) 的排序算法。

您在真实的面试中是否遇到过这个题？是

题目纠错

样例

样例  1:
 输入:  [3, 2, 1, 4, 5]
 输出:  [1, 2, 3, 4, 5]
 
 样例解释: 
 返回排序后的数组。

样例 2:
 输入:  [1, 1, 2, 1, 1]
 输出:  [1, 1, 1, 1, 2]
 
 样例解释: 
 返回排好序的数组。

熟悉各种排序算法

1.冒泡排序：

    public void sortIntegers(int[] A) {
        // 冒泡排序
        //一层控制二层迭代到哪里
        for (int i = 0 ; i < A.length - 1; i++) {
            //二层实现相邻两个元素交换位置，升序，大的放后面
            for (int j = 0; j < A.length - 1 - i; j++) {
                if (A[j] > A[j+1]) {
                    int temp = A[j+1];
                    A[j+1] = A[j];
                    A[j] = temp;
                } 
            } 
        } 
    }

2. 选择排序

选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

    public void sortIntegers(int[] A) {
        // write your code here
        // 选择排序，外层交换最小
        for (int i = 0; i < A.length; i++) {
            //内层，遍历最小
            int minValue = i;
            for (int j = i+1; j < A.length; j++) {
                if (A[minValue] > A[j]) {
                    minValue = j;
                } 
            }
            int temp = A[i];
            A[i] = A[minValue];
            A[minValue] = temp;
        } 
    }

3. 插入排序

插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。