算法 排序算法之选择排序--直接选择排序和堆排序

选择排序

基本思想

每次从待排序的数据元素中选取最大（最小）的数据元素放到数组的最前（最后），数据元素集合不断缩小，当数据元素集合为空时排序结束。

常用的选择排序有：

• 直接选择排序
• 堆排序

堆排序是一种基于完全二叉树的排序

直接选择排序

基本思想

从待排序的集合中选取最小的数据元素并将它原始集合中第一个元素进行交换位置，然后从不包括第一个位置的数据元素集合中选取关键字最小的元素和原始集合中第二个数据元素交换位置，如此重复直到集合中之剩一个元素为止。

排序过程

代码实现

C实现

void SelectSort(DataType a[], int n) {
int i, j, small;
        DataType temp;

for (i = 0; i < a.length - 1; i++) {
            small = i;//设第i个元素最小
for (j = i + 1; j < a.length; j++) {//寻找最小元素
if (a[j] < a[small]) {
                    small = j;//记住最小元素小标
                }
            }
if (small != i) {//当最小元素小标不为i时交换位置
                temp = a[i];
                a[i] = a[small];
                a[small] = temp;
            }
        }
    }

Java实现

  /**
 * 选择排序
 */
public static void selectSort(int[] arr) {
int temp, small;
for (int i = 0; i < arr.length - 1; i++) {
            small = i;//设第i个元素最小
for (int j = i + 1; j < arr.length; j++) {//寻找最小元素
if (arr[j] < arr[small]) {
                    small = j;//记住最小元素小标
                }
            }
if (small != i) {//当最小元素小标不为i时交换位置
                temp = arr[small];
                arr[small] = arr[i];
                arr[i] = temp;
            }
        }
    }

算法分析

• 时间复杂度

  • 比较次数n(n-1)/2 时间复杂度为O(n^2)
• 空间复杂度
  
  • 空间复杂度O（1）
• 稳定性
  
  • 不稳定 每次从无序区选出最小记录与之前最小进行交换造成的
  • 如果在选出最小记录后 将它前面无序的记录一次后移，然后把最小记录放在有序区后面就能保证稳定性

堆排序

基本思想

在直接排序中，待排序的数据元素集合构成一个线性表结构，要从有n个数据的线性表中选出一个最小的元素需要比较n-1次。

如果能把待排序的数据集合构成一个完全二叉树结构，则每次选择处一个最大或者最小的数据只要比较完全二叉树高度次，即log2n次，所以排序的时间复杂度就是O(nlog2n)

堆的定义

最大堆：

设数组a中存放了n个数据元素，数组下标从0开始，如果当数组下标
1. 2i+1<n时，有a[i]>=a[i+1]
2. 2i+2<n时，有a[i]>=a[i+2]
则称这样的数据结构为最大堆

2i+1是左孩子节点 2i+2是右孩子节点

下图就是一个最大堆

• 最大堆的根节点是堆中数值最大的元素，最小堆的根节点是堆中数值最小的元素。称堆的根节点元素为堆顶元素。

• 对于最大堆，从根节点到每个叶节点的路径上，数据元素组成的序列都是递减有序的。

创建堆

从完全二叉树的叶节点开始逐个节点进行调整

1. 对于第一个非叶子节点a[i](i = (n-1)/2)，找出左孩子节点(2i+1)和右孩子节点(2i+2)中的较大者，然后比较这个较大节点和a[i]节点，如果a[i]节点大于等于这个较大节点，则以a[i]为节点的完全二叉树已经满足最大堆的定义，否则对换a[i]和较大节点。
2. 再继续调整第二个非叶子节点a[i-1] 及第三个非叶子节点a[i-2]….
3. 最后调整根节点，根节点调整完毕，这个完全二叉树就满足最大堆的条件了

因为完全二叉树可以直接存储在数组中，把完全二叉树调整为最大堆的过程就是把数组元素按照最大堆的要求进行调整的过程，也称作数组的最大堆化

实例：

初始值

调整第一个非叶节点

调整后的数组

再继续调整第二个非叶节点

将88和10交换后，以10为根节点的二叉树不满足最大堆，因此继续调整

最后的结果

代码实现

C实现

    void CreateHeap(DataType a[], int n, int h) {
int i, j, flag;
        DataType temp;

        i = h;//i为要建堆的二叉树根节点下标
        j = 2 * i + 1; //j为左孩子节点下标
        temp = a[i];
        flag = 0;

/*沿左右孩子中值较大者向下筛选*/
while (j < n && flag != 1) {
/*寻找左右孩子节点中的较大者,j为下标*/
if (j < n - 1 && a[j] < a[j + 1]) {
                j++;
            }

if (temp > a[j]) {
                flag = 1; /*标记筛选结束条件*/
            } else {//否则把a[j]上移
                a[i] = a[j];
                i = j;
                j = 2 * i + 1;
            }
        }
    }

void InitMaxHeap(DataType a[], int n){
int i;
for (i=(n-1)/2;i>=0;i--){
            CreateHeap(a, n, i);
        }
    }

java代码实现

/**
 * 创建最大堆
 *
 * @param arr 数组
 */
private static void createMaxHeap(int[] arr, int length) {
for (int i = (length - 1) / 2; i >= 0; i--) {
            createMaxHeap(arr, length, i);
        }
    }

/**
 * 创建最大堆
 *
 * @param arr 数组
 * @param h 根节点下标
 */
private static void createMaxHeap(int[] arr, int length, int h) {
int i = h;//i为要建堆的二叉树根节点下标
int j = 2 * i + 1; //j为左孩子节点下标

int temp = arr[i];
boolean flag = true;

/*沿左右孩子中值较大者向下筛选*/
while (j < length && flag) {
/*寻找左右孩子节点中的较大者,j为下标*/
if (j < length - 1 && arr[j] < arr[j + 1]) {
                j++;
            }

/*标记筛选结束条件*/
if (temp > arr[j]) {
                flag = false;
            } else {//否则把a[j]上移
                arr[i] = arr[j];
                i = j;
                j = 2 * i + 1;
            }
        }
        arr[i] = temp;
    }

堆排序

循环执行如下直到数组为空

1. 把堆顶a[0]元素与当前最大堆的最后一个元素交换
2. 最大堆元素个数减一
3. 调整数组使之满足对大堆定义

例子：

初始最大堆

把堆顶a[0]元素88与当前最大堆的最后一个元素5交换

将前7个元素继续调整为最大堆

再将根节点和最后一个元素交换

继续重复上述操作

代码实现

C实现

void HeapSort(DataType a[], int n) {
int i;
        DataType temp;

/*创建初始化堆*/
        InitMaxHeap(a, n);

/*当前最大堆个数每次递减1*/
for (i = n - 1; i > 0; i--) {
/*交换堆顶和末尾元素*/
            temp = a[0];
            a[0] = a[i];
            a[i] = temp;
            CreateHeap(a, i, 0);
        }        
    }

java实现

  /**
 * 堆排序
 *
 * @param arr 排序数组
 */
public static void heapSort(int[] arr) {
int temp;
/*创建初始化堆*/
        createMaxHeap(arr, arr.length);
/*当前最大堆个数每次递减1*/
for (int i = arr.length - 1; i > 0; i--) {
/*交换堆顶和末尾元素*/
            temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
/*调整满足最大堆*/
            createMaxHeap(arr, i, 0);
        }
    }

算法分析

• 时间复杂度
  
  • 基于完全二叉树的排序，每次堆顶元素交换后进行调整的时间复杂度均为log2n，所以时间复杂度是O(nlog2n)
• 空间复杂度
  
  • 空间复杂度是O(1)
    -稳定性
  • 堆排序是不稳定的排序算法

---