两种常用的选择排序算法--简单选择排序、堆排序

本文介绍常用的两种选择排序：

1、简单选择排序算法：

时间复杂度为O(n^2)，空间复杂度为O(1)，是不稳定的排序算法

2、堆排序算法：

时间复杂度为O(nlog2n)，空间复杂度为O(1)，是不稳定的排序算法，在数据量较大的时候效率体现得很明显

下面使用java代码来详细讲解这两种排序算法：

1、简单选择排序：

public class SelectRanker {
    private static void swap(int arr[] , int location1, int location2){//交换arr数组中位于location1和location2的元素
        int temp = arr[location1];
        arr[location1] = arr[location2];
        arr[location2] = temp;
    }
    public static void SimpleSelectSort(int[] arr){
        //利用线性查找的方法从一个序列中找到最小的元素
        //具体实现思路为：第i趟排序时，通过n-i次关键字比较，从n-i+1个元素中选出最小的元素并且和i-1(1<=i<=n-1个元素进行交换)
        //时间复杂度为O(n^2) 比较次数较多 移动次数较少 空间复杂度为O(1)(临时变量来记录最小位置) 该排序算法不稳定
        //具体实现代码如下：
        int i , j , minLocation;
        for(i = 0; i<arr.length-1 ;i++){//第i次查找 
            minLocation = i;//记录找到第i小的元素的位置 暂定为i
            for(j = i; j<arr.length; j++){//在i号元素后面找比arr[i]小的元素的位置
                if(arr[j]<arr[i])
                    minLocation = j;//定下当前轮找到的最i小元素位置j
            }
            if(i != minLocation)//如果找到了更小的
                swap(arr, i, minLocation);//交换第i个元素与第i小的元素
        }
    }
}

实现思路为第i趟排序时，选出第i大（小）的元素放在i这个位置，经过数组长度减1次后便完成了排序，实现细节见注释。

2、堆排序

就是通过最大（小）堆移除根结点，每次移除都能得到一个最大（小）的结点。最大堆的实现之前写过，详情见这。