选择排序+堆排序（选直堆）

ava中的经典算法之选择排序（SelectionSort）

排序算法（四）选择排序及优化版本

“深入理解”—选择排序算法

 

 

选择排序的思想：选出最小的一个和第一个位置交换，选出其次小的和第二个位置交换 ……

 

直到从第N个和第N-1个元素中选出最小的放在第N-1个位置。

 

a) 原理：每一趟从待排序的记录中选出最小的元素，顺序放在已排好序的序列最后，直到全部记录排序完毕。也就是：每一趟在n-i+1(i=1，2，…n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录。基于此思想的算法主要有简单选择排序、树型选择排序和堆排序。（这里只介绍常用的简单选择排序）

 

b) 简单选择排序的基本思想：给定数组：int[] arr={里面n个数据}；第1趟排序，在待排序数据arr[1]~arr[n]中选出最小的数据，将它与arrr[1]交换；第2趟，在待排序数据arr[2]~arr[n]中选出最小的数据，将它与r[2]交换；以此类推，第i趟在待排序数据arr[i]~arr[n]中选出最小的数据，将它与r[i]交换，直到全部排序完成。

 

c) 举例：数组 int[] arr={5,2,8,4,9,1};

-------------------------------------------------------

第一趟排序： 原始数据：5  2  8  4  9  1

最小数据1，把1放在首位，也就是1和5互换位置，

排序结果：1  2  8  4  9  5

 

-------------------------------------------------------

 

第二趟排序：

第1以外的数据{2  8  4  9  5}进行比较，2最小，

排序结果：1  2  8  4  9  5

-------------------------------------------------------

 

第三趟排序：

除1、2以外的数据{8  4  9  5}进行比较，4最小，8和4交换

排序结果：1  2  4  8  9  5

-------------------------------------------------------

 

第四趟排序：

除第1、2、4以外的其他数据{8  9  5}进行比较，5最小，8和5交换

排序结果：1  2  4  5  9  8

-------------------------------------------------------

 

第五趟排序：

除第1、2、4、5以外的其他数据{9  8}进行比较，8最小，8和9交换

排序结果：1  2  4  5  8  9

-------------------------------------------------------

 

注：每一趟排序获得最小数的方法：for循环进行比较，定义一个第三个变量temp，首先前两个数比较，把较小的数放在temp中，然后用temp再去跟剩下的数据比较，如果出现比temp小的数据，就用它代替temp中原有的数据。具体参照后面的代码示例，相信你在学排序之前已经学过for循环语句了，这样的话，这里理解起来就特别容易了。

 

//选择排序
public class SelectionSort {
    public static void main(String[] args) {
        int[] arr={1,3,2,45,65,33,12};     
        //选择排序的优化
        for(int i = 0; i < arr.length - 1; i++) {// 做第i趟排序
            int k = i;
            for(int j = k + 1; j < arr.length; j++){// 选最小的记录
                if(arr[j] < arr[k]){ 
                    k = j; //记下目前找到的最小值所在的位置
                }
            }
            //在内层循环结束，也就是找到本轮循环的最小的数以后，再进行交换
            if(i != k){  //交换a[i]和a[k]
                int temp = arr[i];
                arr[i] = arr[k];
                arr[k] = temp;
            }    
        }        
    }
}

 选择排序及其复杂度分析

选择排序的复杂度分析。第一次内循环比较N - 1次，然后是N-2次，N-3次，……，最后一次内循环比较1次。共比较的次数是 (N - 1) + (N - 2) + ... + 1，求等差数列和，得 (N - 1 + 1)* N / 2 = N^2 / 2。

舍去最高项系数，其时间复杂度为 O(N^2)。

 

虽然选择排序和冒泡排序的时间复杂度一样，但实际上，选择排序进行的交换操作很少，最多会发生 N - 1次交换。

而冒泡排序最坏的情况下要发生N^2 /2交换操作。从这个意义上讲，交换排序的性能略优于冒泡排序。

 

 

优化版本： 

根据上边的分析，如果在每一次查找最小值的时候，也可以找到一个最大值，然后将两者分别放在它们应该出现的位置，这样遍历的次数就比较少了，下边给出代码实现：

 

void SelectSort(vector<int>& a)
{
    int left = 0;
    int right = a.size() - 1;
    int min = left;//存储最小值的下标
    int max = left;//存储最大值的下标
    while(left <= right)
    {
        min = left;
        max = left;
        for(int i = left; i <= right; ++i)
        {
            if(a[i] < a[min])
            {
                min = i;
            }
            if(a[i] > a[max])
            {
                max = i;
            }
        }
        swap(a[left],a[min]);
        if(left == max)
            max = min;
        swap(a[right],a[max]);

        ++left;
        --right;
    }
}

 这样总共遍历的次数比起前边的一般版本就会减少一半，时间复杂度是O(N/2 * N /2)还是O(N*N)。但是，代码中，第一次交换结束后，如果left那个位置原本放置的就是最大数，交换之后，需要将最大数的下标还原。 

需要注意的是，每次记住的最小值或者最大值的下标，这样方便进行交换。

 

2、堆排序

 完全二叉树

      若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树

图解排序算法(三)之堆排序

百度经验-堆排序算法解析

 

堆排序

　　堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。首先简单了解下堆结构。

堆

　　堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。如下图：

 

同时，我们对堆中的结点按层进行编号，将这种逻辑结构映射到数组中就是下面这个样子

 

该数组从逻辑上讲就是一个堆结构，我们用简单的公式来描述一下堆的定义就是：

大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]  

小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]  

ok，了解了这些定义。接下来，我们来看看堆排序的基本思想及基本步骤：

堆排序基本思想及步骤

　　堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了

 

再简单总结下堆排序的基本思路：

　　a.将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;

　　b.将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;

　　c.重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

 

package com.test;

import java.util.Arrays;

public class HeapSort {
	public static void main(String[] args) {
		int[] arr = { 4, 6, 8, 5, 9};
		sort(arr);
		System.out.println(Arrays.toString(arr));
	}

	
	public static void sort(int[] arr) {
		// 1.构建大顶堆
		for (int i = arr.length / 2 - 1; i >= 0; i--) {
			// 从第一个非叶子结点从下至上，从右至左调整结构
			adjustHeap(arr, i, arr.length);
		}
		// 2.调整堆结构+交换堆顶元素与末尾元素
		for (int j = arr.length - 1; j > 0; j--) {
			swap(arr, 0, j);// 将堆顶元素与末尾元素进行交换
			adjustHeap(arr, 0, j);// 重新对堆进行调整
		}

	}

	/**
	 * 调整大顶堆（仅是调整过程，建立在大顶堆已构建的基础上）
	 * 
         *  从最后一个非叶子节点（a.length/2 - 1）开始，处理完后，K为其值大的叶子节点；
         *  此时K下面没有叶子节点，所以要依次往最后一个非叶子节点的根节点去调整置换
	 * @param arr
	 * @param i
	 * @param length
	 */
	public static void adjustHeap(int[] arr, int i, int length) {
		int temp = arr[i];// 先取出当前元素i
		
		//k = k*2+1是循环调整当前K节点的下面的堆
		for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {// 从i结点的左子结点开始，也就是2i+1处开始
			if (k + 1 < length && arr[k] < arr[k + 1]) {// 如果左子结点小于右子结点，k指向右子结点
				k++;
			}
			if (arr[k] > temp) {// 如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
				//arr[i] = arr[k];
				swap(arr,i,k);
				i = k;
			} else {
				break;
			}
		}
		//arr[i] = temp;// 将temp值放到最终的位置
	}

	/**
	 * 交换元素
	 * 
	 * @param arr
	 * @param a
	 * @param b
	 */
	public static void swap(int[] arr, int a, int b) {
		int temp = arr[a];
		arr[a] = arr[b];
		arr[b] = temp;
	}
}

 

堆排序是一种选择排序，整体主要由构建初始堆+交换堆顶元素和末尾元素并重建堆两部分组成。其中构建初始堆经推导复杂度为O(n)，在交换并重建堆的过程中，需交换n-1次，而重建堆的过程中，根据完全二叉树的性质，[log2(n-1),log2(n-2)...1]逐步递减，近似为nlogn。所以堆排序时间复杂度一般认为就是O(nlogn)级。