数据结构和算法系列6 七大排序之直接选择排序和堆排序

时间：2022-06-24 22:10:59

上一篇我们总结了交换排序的冒泡排序和快速排序。那么这一篇我们要总结的是选择排序，选择排序分为直接选择排序和堆排序，我们主要分以下几点进行总结。

1，直接选择排序及算法实现

2，堆排序及算法实现

1，直接选择排序及算法实现

直接选择排序(Straight Select Sort)是一种简单的排序方法，它的基本思想是：通过n-i次关键字之间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i(1<=i<=n)个记录交换位置。

比如，下图展示了直接选择排序的过程。

 

下面是算法的实现代码。

C#版：

namespace SelectionSort.CSharp
{
class Program
    {
static void Main(string[] args)
        {
            List<int> list = new List<int> { 50, 10, 90, 30, 70, 40, 80, 60, 20 };
            Console.WriteLine("********************直接选择排序********************");
            Console.WriteLine("排序前：");
            Display(list);

            Console.WriteLine("排序后：");
            SelectionSort(list);
            Display(list);

            Console.ReadKey();
        }

/// <summary>
/// 直接选择排序算法
/// </summary>
/// <returns>排序后的list</returns>
public static void SelectionSort(List<int> list)
        {
//要遍历的次数(遍历n-1次)
for (int i = 0; i < list.Count-1 ; i++)
            { 
//将当前下标定义为最小值下标
int min = i;

//遍历之后的数据
for (int j = i + 1; j <= list.Count-1; j++)
                {
//如果有小于当前最小值的关键字，将它的下标赋值给min
if (list[min] > list[j]) min = j;
                }

//若min不等于i，说明找到真正最小值，交换真正最小值与之前假设最小值的位置
if (i != min) Swap(list,i,min);
            }
        }

private static void Swap(List<int> list, int i, int min)
        { 
int temp=list[i];
            list[i]=list[min];
            list[min] = temp;
        }

/// <summary>
/// 打印列表元素
/// </summary>
/// <param name="list"></param>
private static void Display(List<int> list)
        {
            Console.WriteLine("\n**********展示结果**********\n");

if (list != null && list.Count > 0)
            {
foreach (var item in list)
                {
                    Console.Write("{0} ", item);
                }
            }

            Console.WriteLine("\n**********展示完毕**********\n");
        }
    }
}

程序运行结果：

数据结构和算法系列6 七大排序之直接选择排序和堆排序

 

C语言版：

/*包含头文件*/
#include "stdio.h"
#include "stdlib.h"   
#include "io.h"
#include "math.h" 
#include "time.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100

typedef int Status; 
typedef struct
{
int data[MAXSIZE];
int length;    
}SeqList;

/*交换
*注意要先声明方法，然后再调用，否则会报错
*/
void Swap(SeqList *seqList,int i,int min)
{
int temp;
    temp=seqList->data[i];
    seqList->data[i]=seqList->data[min];
    seqList->data[min]=temp;
}

/*直接选择排序*/
void SelectionSort(SeqList *seqList)
{
int i,j,min;

//要遍历的次数(遍历n-1次)
for (i=0;i<seqList->length-1;i++)
    {
//将当前下标定义为最小值下标
        min=i;

//遍历之后的数据
for (j=i+1;j<=seqList->length-1;j++)
        {
//如果有小于当前最小值的关键字，将它的下标赋值给min
if (seqList->data[min]>seqList->data[j]) min=j;
        }

//若min不等于i，说明找到真正最小值，交换真正最小值与之前假设最小值的位置
if (i != min) Swap(seqList,i,min);
    }
}

/*打印结果*/
void Display(SeqList *seqList)
{
int i;
    printf("\n**********展示结果**********\n");

for (i=0;i<seqList->length;i++)
    {
        printf("%d ",seqList->data[i]);
    }

    printf("\n**********展示完毕**********\n");
}

#define N 9
void main()
{
int i,j;
    SeqList seqList;

//定义数组和初始化SeqList
int d[N]={50,10,90,30,70,40,80,60,20};

for (i=0;i<N;i++)
    {
        seqList.data[i]=d[i];
    }
    seqList.length=N;

    printf("***************直接选择排序***************\n");
    printf("排序前：");
    Display(&seqList);

    SelectionSort(&seqList);
    printf("\n排序后：");
    Display(&seqList);

    getchar();
}

运行结果同C#版

2，堆排序及算法实现

堆排序(Heap Sort) 利用堆（一般为大根堆）进行排序的方法。它的基本思想是：将待排序的序列构造成一个大根堆。此时，整个序列的最大值就是堆顶的根结点。将它移走（其实就是将其与堆数组的末尾元素进行交换，此时末尾元素就是最大值），然后将剩余的n-1个序列重新构造成一个大根堆，这样就会得到n个元素中的次大值。如此反复执行，便能得到一个有序序列了。

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

下面是其实现代码。

C#版：

namespace HeapSort.CSharp
{
class Program
    {
static void Main(string[] args)
        {
            List<int> list = new List<int> { 50, 10, 90, 30, 70, 40, 80, 60, 20 };
            Console.WriteLine("********************堆排序********************");
            Console.WriteLine("排序前：");
            Display(list);

            Console.WriteLine("排序后：");
            HeapSort(list);
            Display(list);

            Console.ReadKey();
        }

/// <summary>
/// 堆排序算法
/// </summary>
/// <param name="list"></param>
public static void HeapSort(List<int> list)
        {
//将无序堆构造成一个大根堆,大根堆有list.Count/2个父结点
for (int i = list.Count / 2 - 1; i >= 0;i-- )
            {
                HeadAdjust(list,i,list.Count);
            }

//逐步将每个最大值的根结点与末尾元素交换，并且再调整其为大根堆
for (int i = list.Count - 1; i > 0; i--)
            {
//将堆顶记录和当前未经排序子序列的最后一个记录交换位置
                Swap(list,0,i);
                HeadAdjust(list,0,i);
            }
        }

/// <summary>
/// 构造大根堆
/// </summary>
/// <param name="list"></param>
/// <param name="parent"></param>
/// <param name="length"></param>
public static void HeadAdjust(List<int> list, int parent, int length)
        { 
//保存当前父结点
int temp=list[parent];

//得到左孩子结点
int leftChild = 2 * parent + 1;

while (leftChild < length)
            {
//如果parent有右孩子，则要判断左孩子是否小于右孩子
if (leftChild + 1 < length && list[leftChild] < list[leftChild + 1])
                    leftChild++;

//父亲节点大于子节点，就不用做交换
if (temp >= list[leftChild])
break;

//将较大子节点的值赋给父亲节点
                list[parent] = list[leftChild];

//然后将子节点做为父亲节点，已防止是否破坏根堆时重新构造
                parent = leftChild;

//找到该父亲节点较小的左孩子节点
                leftChild = 2 * parent + 1;
            }
//最后将temp值赋给较大的子节点，以形成两值交换
            list[parent] = temp;
        }

#region Private Method

private static void Swap(List<int> list, int top, int last)
        {
int temp = list[top];
            list[top] = list[last];
            list[last] = temp;
        }

private static void Display(List<int> list)
        {
            Console.WriteLine("\n**********展示结果**********\n");

if (list != null && list.Count > 0)
            {
foreach (var item in list)
                {
                    Console.Write("{0} ", item);
                }
            }

            Console.WriteLine("\n**********展示完毕**********\n");
        }

#endregion
    }
}

程序运行结果：

数据结构和算法系列6 七大排序之直接选择排序和堆排序

 

C语言版：

/*包含头文件*/
#include "stdio.h"
#include "stdlib.h"   
#include "io.h"
#include "math.h" 
#include "time.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100

typedef int Status; 
typedef struct
{
int data[MAXSIZE];
int length;    
}SeqList;

/*构造大根堆*/
void HeapAdjust(SeqList *seqList,int parent,int length)
{
int temp,leftChild;

    temp=seqList->data[parent];
    leftChild = 2 * parent + 1;

while (leftChild < length)
    {
if (leftChild + 1 < length && seqList->data[leftChild]<seqList->data[leftChild+1]) 
            leftChild++;

if (temp >= seqList->data[leftChild])
break;

        seqList->data[parent]=seqList->data[leftChild];

        parent = leftChild;

        leftChild = 2 * parent + 1;
    }
    seqList->data[parent] = temp;
}

/*交换元素*/
void Swap(SeqList *seqList,int top,int last)
{
int temp=seqList->data[top];
    seqList->data[top]=seqList->data[last];
    seqList->data[last]=temp;
}

/*堆排序算法*/
void HeapSort(SeqList *seqList)
{
int i;
for (i=seqList->length/2-1;i>=0;i--)
    {
        HeapAdjust(seqList,i,seqList->length);
    }

for (i=seqList->length-1;i>0;i--)
    {
        Swap(seqList,0,i);
        HeapAdjust(seqList,0,i);
    }
}

/*打印结果*/
void Display(SeqList *seqList)
{
int i;
    printf("\n**********展示结果**********\n");

for (i=0;i<seqList->length;i++)
    {
        printf("%d ",seqList->data[i]);
    }

    printf("\n**********展示完毕**********\n");
}

#define N 9
void main()
{
int i,j;
    SeqList seqList;

//定义数组和初始化SeqList
int d[N]={50,10,90,30,70,40,80,60,20};

for (i=0;i<N;i++)
    {
        seqList.data[i]=d[i];
    }
    seqList.length=N;

    printf("***************堆排序***************\n");
    printf("排序前：");
    Display(&seqList);

    HeapSort(&seqList);
    printf("\n排序后：");
    Display(&seqList);

    getchar();
}

程序运行结果同上

标签：

相关文章