排序算法003-选择排序


首先要知道选择排序包括:简单选择排序,堆排序


选择排序的基本思想

每一趟从待排序的数据中选出最小元素,顺序放在已排好序的数据最后,直到全部数据排序完毕。



一、简单选择排序(不稳定、O(N2)


1. 算法思想:

 

对于一组数据,如待排序的数据{K1,K2,…,Kn},首先从数据中寻找最小值,我们假定是Kn , 那么我们要把Kn和K1来交换,就是把最小值移动到最前面,然后从除K1外的剩下的元素去寻找另一个最小值,然后和K2交换,就这样依次类推,直到元素的最后!


2. 演示动画

happysneaker.com


3. Java 实现

 
import java.util.Random;
 
public class SelectionSort {

    public void selectionSort(int[] list) {
        // 需要遍历获得最小值的次数
        // 要注意一点,当要排序 N 个数,已经经过 N-1 次遍历后,已经是有序数列
        for (int i = 0; i < list.length - 1; i++) {
            int temp = 0; // 待会交换数字时候用的辅助数
            int index = i; // 用来保存最小值的索引

            // 寻找第i个小的数值,这个for循环结束后,index存的就是最小值的下标
            for (int j = i + 1; j < list.length; j++) {
                if (list[index] > list[j]) {
                    index = j;
                }
            }
 
            // 将最小值放在开头位置,即开头位置数字与最小值交换位置
            temp = list[index];
            list[index] = list[i];
            list[i] = temp;

            System.out.format("第 %d 趟:\t", i + 1);
            printAll(list);
        }
    }
 
    // 打印完整序列
    public void printAll(int[] list) {
        for (int value : list) { // 类似循环的作用
            System.out.print(value + "\t");
        }
        System.out.println(); // 回车
    }
 
    // 主函数
    public static void main(String[] args) {
        // 初始化一个随机序列
        final int MAX_SIZE = 10;
        int[] array = new int[MAX_SIZE];
        Random random = new Random();
        for (int i = 0; i < MAX_SIZE; i++) {
            array[i] = random.nextInt(100); // 0-99随机生成数字
        }
 
        // 调用冒泡排序方法
        SelectionSort selection = new SelectionSort(); // 声明一个类的对象方便调用方法
        System.out.print("排序前:\t");
        selection.printAll(array);
        
        selection.selectionSort(array); // 进行排序
        
        System.out.print("排序后:\t");
        selection.printAll(array);
    }
 
}

运行结果:

happysneaker.com




二、堆排序(不稳定,O(nlogn),构建堆的过程的时间复杂度为n,调堆的时间复杂度为logn


1.  想要要学习堆排序,得知道什么是完全二叉树,完全二叉树就是在第n层被填满之前,不会开始填第n+1层深度,并且是从左向右填满。

happysneaker.com

2. 那什么是堆排序呢?


    堆是近似于完全二叉树的一种数据结构。由于其它几种堆(二项式堆,斐波纳契堆等)用的较少,一般将二叉堆就简称为堆。

    堆排序就是利用完全完全二叉树()的性质进行排序。又分为最大堆和最小堆:

         最大堆:父节点的键值总是大于或者等于任何一个子节点的键值。

         最小堆:父节点的键值总是小于或者等于任何一个子节点的键值。

如下图就是一个最小堆:

happysneaker.com


堆排序的实现可以分为两个子算法:初始建堆进行堆排序


3. 堆排序分析:

(1)堆的存储:

一般都用数组来表示堆,i结点的父结点下标就为(i – 1) / 2。它的左右子结点下标分别为2 * i + 1和2 * i + 2。如第0个结点左右子结点下标分别为1和2(注意取整,0.5就是0,1.5就是1)

或者表示为  (最小堆)Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]

                    (最大堆)Key[i]>=Key[2i+1]&&key[i]>=key[2i+2]

happysneaker.com


(2)堆的操作——插入、删除

    2-1、堆的插入

           每次插入都是将新数据放在数组最后。可以发现从这个新数据的父结点到根结点必然为一个有序的数列,现在的任务是将这个新数据插入到这个有序数据中——这就类似于直接插入排序中将一个数据并入到有序区间中,代码如下:

        1. //  新加入i结点  其父结点为(i - 1) / 2  

        2. void MinHeapFixup(int a[], int i)  

        3. {  

        4.     int j, temp;  

        5.       

        6.     temp = a[i];  

        7.     j = (i - 1) / 2;      //父结点  

        8.     while (j >= 0 && i != 0)  

        9.     {  

        10.         if (a[j] <= temp)  

        11.             break;  

        12.           

        13.         a[i] = a[j];     //把较大的子结点往下移动,替换它的子结点  

        14.         i = j;  

        15.         j = (i - 1) / 2;  

        16.     }  

        17.     a[i] = temp;  

          更简短的表达为:

        1. void MinHeapFixup(int a[], int i)  

        2. {  

        3.     for (int j = (i - 1) / 2; (j >= 0 && i != 0)&& a[i] > a[j]; i = j, j = (i - 1) / 2)  

        4.         Swap(a[i], a[j]);  

        5. }  

            插入时:

        1. //在最小堆中加入新的数据nNum  

        2. void MinHeapAddNumber(int a[], int n, int nNum)  

        3. {  

        4.     a[n] = nNum;  

        5.     MinHeapFixup(a, n);  

        6. }  


    2-2、堆的删除

           按定义,堆中每次都只能删除第0个数据。为了便于重建堆,实际的操作是将最后一个数据的值赋给根结点,然后再从根结点开始进行一次从上向下的调整。调整时先在左右儿子结点中找最小的,如果父结点比这个最小的子结点还小说明不需要调整了,反之将父结点和它交换后再考虑后面的结点。相当于从根结点将一个数据的“下沉”过程。下面给出代码:

        1. //  从i节点开始调整,n为节点总数 从0开始计算 i节点的子节点为 2*i+1, 2*i+2  

        2. void MinHeapFixdown(int a[], int i, int n)  

        3. {  

        4.     int j, temp;  

        5.   

        6.     temp = a[i];  

        7.     j = 2 * i + 1;  

        8.     while (j < n)  

        9.     {  

        10.         if (j + 1 < n && a[j + 1] < a[j]) //在左右孩子中找最小的  

        11.             j++;  

        12.   

        13.         if (a[j] >= temp)  

        14.             break;  

        15.   

        16.         a[i] = a[j];     //把较小的子结点往上移动,替换它的父结点  

        17.         i = j;  

        18.         j = 2 * i + 1;  

        19.     }  

        20.     a[i] = temp;  

        21. }  

        22. //在最小堆中删除数  

        23. void MinHeapDeleteNumber(int a[], int n)  

        24. {  

        25.     Swap(a[0], a[n - 1]);  

        26.     MinHeapFixdown(a, 0, n - 1);  

        27. }  


      2-3、堆化数组

            有了堆的插入和删除后,再考虑下如何对一个数据进行堆化操作。要一个一个的从数组中取出数据来建立堆吧,不用!先看一个数组,如下图:

happysneaker.com

            很明显,对叶子结点来说,可以认为它已经是一个合法的堆了即20,60, 65, 4, 49都分别是一个合法的堆。只要从A[4]=50开始向下调整就可以了。然后再取A[3]=30,A[2] = 17,A[1] = 12,A[0] = 9分别作一次向下调整操作就可以了。下图展示了这些步骤:

happysneaker.com

            写出堆化数组的代码:

        1. //建立最小堆  

        2. void MakeMinHeap(int a[], int n)  

        3. {  

        4.     for (int i = n / 2 - 1; i >= 0; i--)  

        5.         MinHeapFixdown(a, i, n);  

        6. }  

至此,堆的操作就全部完成了(注1),再来看下如何用堆这种数据结构来进行排序。


       2-4、堆排序

          首先可以看到堆建好之后堆中第0个数据是堆中最小的数据。取出这个数据再执行下堆的删除操作。这样堆中第0个数据又是堆中最小的数据,重复上述步骤直至堆中只有一个数据时就直接取出这个数据。

          由于堆也是用数组模拟的,故堆化数组后,第一次将A[0]与A[n - 1]交换,再对A[0…n-2]重新恢复堆。第二次将A[0]与A[n – 2]交换,再对A[0…n - 3]重新恢复堆,重复这样的操作直到A[0]与A[1]交换。由于每次都是将最小的数据并入到后面的有序区间,故操作完成后整个数组就有序了。有点类似于直接选择排序

        1. void MinheapsortTodescendarray(int a[], int n)  

        2. {  

        3.     for (int i = n - 1; i >= 1; i--)  

        4.     {  

        5.         Swap(a[i], a[0]);  

        6.         MinHeapFixdown(a, 0, i);  

        7.     }  

        8. }  

注意使用最小堆排序后是递减数组,要得到递增数组,可以使用最大堆。

由于每次重新恢复堆的时间复杂度为O(logN),共N - 1次重新恢复堆操作,再加上前面建立堆时N / 2次向下调整,每次调整时间复杂度也为O(logN)。二次操作时间相加还是O(N * logN)。故堆排序的时间复杂度为O(N * logN)。


4. C++ 实现

#include <iostream>
#include<algorithm>
using namespace std;

void HeapAdjust(int *a,int i,int size)  //调整堆 
{
    int lchild=2*i;       //i的左孩子节点序号 
    int rchild=2*i+1;     //i的右孩子节点序号 
    int max=i;            //临时变量 
    if(i<=size/2)          //如果i是叶节点就不用进行调整 
    {
        if(lchild<=size&&a[lchild]>a[max])
        {
            max=lchild;
        }    
        if(rchild<=size&&a[rchild]>a[max])
        {
            max=rchild;
        }
        if(max!=i)
        {
            swap(a[i],a[max]);
            HeapAdjust(a,max,size);    //避免调整之后以max为父节点的子树不是堆 
        }
    }        
}

void BuildHeap(int *a,int size)    //建立堆 
{
    int i;
    for(i=size/2;i>=1;i--)    //非叶节点最大序号值为size/2 
    {
        HeapAdjust(a,i,size);    
    }    
} 

void HeapSort(int *a,int size)    //堆排序 
{
    int i;
    BuildHeap(a,size);
    for(i=size;i>=1;i--)
    {
        //cout<<a[1]<<" ";
        swap(a[1],a[i]);           //交换堆顶和最后一个元素,即每次将剩余元素中的最大者放到最后面 
          //BuildHeap(a,i-1);        //将余下元素重新建立为大顶堆 
          HeapAdjust(a,1,i-1);      //重新调整堆顶节点成为大顶堆
    }
} 

int main(int argc, char *argv[])
{
     //int a[]={0,16,20,3,11,17,8};
    int a[100];
    int size;
    while(scanf("%d",&size)==1&&size>0)
    {
        int i;
        for(i=1;i<=size;i++)
            cin>>a[i];
        HeapSort(a,size);
        for(i=1;i<=size;i++)
            cout<<a[i]<<"";
        cout<<endl;
    }
    return 0;
}


Unity那些事儿
请先登录后发表评论
  • 最新评论
  • 总共0条评论