直接插入排序、希尔排序、直接选择排序、堆排序、冒泡排序——“数据结构与算法”

排序的概念及其运用

排序的概念

• 排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
• 稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
• 内部排序：数据元素全部放在内存中的排序。
• 外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

排序运用

常见的排序算法

常见排序算法的实现

插入排序

基本思想 ：

插入排序是一种简单的插入排序法 ， 其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。

实际中我们玩扑克牌时，就用了插入排序的思想

直接插入排序：

当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移

//直接插入排序
void InsertSort(int* a, int n)
{
  int i = 0;
  for (i = 1; i < n; i++)
  {
        //[0,end]有序，插入tmp依旧有序
    int end = i - 1;
    int tmp = a[i];
    while (end >= 0)
    {
      //插入的数据比原来的数据小
      if (a[end] > tmp)
      {
        a[end + 1] = a[end];
        --end;
      }
      else
      {
        break;
      }
    }
    a[end + 1] = tmp;
  }
}

直接插入排序的特性总结：

1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)，它是一种稳定的排序算法
4. 稳定性：稳定

希尔排序( 缩小增量排序 )

希尔排序法又称缩小增量法。

希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取重复上述分组和排序的工 作。当到达=1时，所有记录在统一组内排好序。

• gap越大，大的数可以更快的到后面，小的数可以更快的到前面，越不接近有序
• gap越小，大的小的挪动越慢，但是它越接近有序
• gap==1，就是直接插入排序

void ShellSort(int* a, int n)
{
  //1.gap>1,预排序
  //2.gap==1,直接插入排序
  int gap = n;
  while (gap > 1)
  {
    gap = gap / 3 + 1;
    //+1可以保证最后一次一定是1
    for (int i = 0; i < n - gap; i++)
                        //防止越界
    {
      int end = i;
      int tmp = a[end + gap];
      while (end >= 0)
      {
        if (a[end] > tmp)
        {
          a[end + gap] = a[end];
          end = end - gap;
        }
        else
        {
          break;
        }
      }
      a[end + gap] = tmp;
    }
  }
}

希尔排序的特性总结：

• 希尔排序是对直接插入排序的优化。
• 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就 会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
• 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定：

《数据结构(C语言版)》--- 严蔚敏

《数据结构-用面相对象方法与C++描述》--- 殷人昆

• 稳定性：不稳定

暂且认为希尔排序的时间复杂度是O(N^1.3)！！！

测试一下直接插入排序和希尔排序：

void TestInsertSort()
{
  int a[] = { 2,1,4,3,6,5,7,9,8,10 };
  PrintArray(a, sizeof(a) / sizeof(a[0]));
  InsertSort(a, sizeof(a) / sizeof(a[0]));
  PrintArray(a, sizeof(a) / sizeof(a[0]));
}
void TestShellSort()
{
  int a[] = { 2,1,4,3,6,5,7,9,8,10 };
  PrintArray(a, sizeof(a) / sizeof(a[0]));
  ShellSort(a, sizeof(a) / sizeof(a[0]));
  PrintArray(a, sizeof(a) / sizeof(a[0]));
}

选择排序

基本思想：

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。

直接选择排序:

• 在元素集合array[i]--array[n-1]中选择关键码最大(小)的数据元素
• 若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换
• 在剩余的array[i]--array[n-2]（array[i+1]--array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素

void Swap(int* a1, int* a2)
{
  int tmp = *a1;
  *a1 = *a2;
  *a2 = tmp;
}
void SelectSort(int* a, int n)
{
  int begin = 0;
  int end = n - 1;
  while (begin < end)
  {
    int maxi = begin;
    int mini = begin;
    for (int i = begin; i <= end; i++)
    {
      if (a[i] > a[maxi])
      {
        maxi = i;
      }
      if (a[i] < a[mini])
      {
        mini = i;
      }
    }
    Swap(&a[begin], &a[mini]);
    //如果maxi和begin重叠，修正一下即可
    if (begin ==maxi)
    {
      maxi = mini;
    }
    Swap(&a[end], &a[maxi]);
    ++begin;
    --end;
  }
}

直接选择排序的特性总结：

1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：不稳定

堆排序

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。

//向下调整算法
void AdjustDown(int* a, int n, int parent)
{
  //默认左孩子小
  int child = parent * 2 + 1;
  while (child < n)//孩子在数组范围内
  {
    //选出左右孩子中大的那一个
    //有可能假设错了
    //左孩子不存在，一定没有右孩子——完全二叉树
    //左孩子存在，有可能没有右孩子
    if (child + 1 < n && a[child + 1] > a[child])
      //  右孩子存在     右孩子>左孩子
      //不能这么写 if (a[child + 1] > a[chid] && child + 1 < n )
      //这样写会有越界的风险 因为是先访问了数组中的元素 再去比较右孩子是否存在
    {
      ++child;
    }
    //child就是大的那个孩子
    //不关心到底是左孩子还是右孩子 
    if (a[child] > a[parent])
    {
      Swap(&a[child], &a[parent]);
      parent = child;
      child = parent * 2 + 1;//默认又算的是左孩子
    }
    else
    {
      break;
    }
 
  }
}
void HeapSort(int* a, int n)
{
  //建堆——向下调整建堆
  int i = 0;
  for (i = (n - 1 - 1) / 2; i >= 0; i--)
  {
    AdjustDown(a, n, i);
  }
  //升序——建大堆
  int end = n - 1;
  while (end > 0)
  {
    Swap(&a[0], &a[end]);
    AdjustDown(a, end, 0);
    --end;
  }
}

堆排序的特性总结：

1. 堆排序使用堆来选数，效率就高了很多。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(1)
4. 稳定性：不稳定

测试一下直接选择排序和堆排序：

void TestSelectSort()
{
  int a[] = { 2,1,4,3,6,5,7,9,8,10 };
  PrintArray(a, sizeof(a) / sizeof(a[0]));
  SelectSort(a, sizeof(a) / sizeof(a[0]));
  PrintArray(a, sizeof(a) / sizeof(a[0]));
}
void TestHeapSort()
{
  int a[] = { 2,1,4,3,6,5,7,9,8,10 };
  PrintArray(a, sizeof(a) / sizeof(a[0]));
  HeapSort(a, sizeof(a) / sizeof(a[0]));
  PrintArray(a, sizeof(a) / sizeof(a[0]));
}

交换排序

基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

冒泡排序

void BubbleSort(int* a, int n)
{
  for (int j = 0; j < n; j++)
  {
    bool exchange = false;
    for (int i = 1; i < n - j; i++)
    {
      if (a[i - 1] > a[i])
      {
        int tmp = a[i];
        a[i] = a[i - 1];
        a[i - 1] = tmp;
        exchange = true;
      }
    }
    if (exchange == false)
    {
      break;
    }
  }
}

冒泡排序的特性总结：

1. 冒泡排序是一种非常容易理解的排序
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：稳定

总结

测试一下上述五大排序的性能：

// 测试排序的性能对比
void TestOP()
{
  srand(time(0));
  const int N = 100000;
  int* a1 = (int*)malloc(sizeof(int) * N);
  int* a2 = (int*)malloc(sizeof(int) * N);
  int* a3 = (int*)malloc(sizeof(int) * N);
  int* a4 = (int*)malloc(sizeof(int) * N);
  int* a5 = (int*)malloc(sizeof(int) * N);
  int* a6 = (int*)malloc(sizeof(int) * N);
  int* a7 = (int*)malloc(sizeof(int) * N);
 
  for (int i = 0; i < N; ++i)
  {
    a1[i] = rand();
    a2[i] = a1[i];
    a3[i] = a1[i];
    a4[i] = a1[i];
    a5[i] = a1[i];
    a6[i] = a1[i];
    a7[i] = a1[i];
  }
  int begin1 = clock();
  InsertSort(a1, N);
  int end1 = clock();
 
  int begin2 = clock();
  ShellSort(a2, N);
  int end2 = clock();
 
  int begin3 = clock();
  SelectSort(a3, N);
  int end3 = clock();
 
  int begin4 = clock();
  HeapSort(a4, N);
  int end4 = clock();
 
    int begin7 = clock();
  BubbleSort(a7, N);
  int end7 = clock();
 
  printf("InsertSort:%d\n", end1 - begin1);
  printf("ShellSort:%d\n", end2 - begin2);
  printf("SelectSort:%d\n", end3 - begin3);
  printf("HeapSort:%d\n", end4 - begin4);
 
 
  printf("BubbleSort:%d\n", end7 - begin7);
    
    free(a1);
  free(a2);
  free(a3);
  free(a4);
  free(a5);
  free(a6);
  free(a7);
}

测试性能最好使用Release版本！！！

通过上面这幅图，我们可以发现：冒泡排序和直接选择排序的性能较差，直接插入排序性能中等水平，希尔排序和堆排序的性能较好。

上面所有排序的源代码：

Sort.c的内容：

#include"Sort.h"
void PrintArray(int* a, int n)
{
   int i = 0;
   for (i = 0; i < n; i++)
   {
       printf("%d ", a[i]);
   }
   printf("\n");
}
void InsertSort(int* a, int n)
{
   int i = 0;
   for (i = 1; i < n; i++)
   {
       int end = i - 1;
       int tmp = a[i];
       while (end >= 0)
       {
           //插入的数据比原来的数据小
           if (a[end] > tmp)
           {
               a[end + 1] = a[end];
               --end;
           }
           else
           {
               break;
           }
       }
       a[end + 1] = tmp;
   }
}

void ShellSort(int* a, int n)
{
   //1.gap>1,预排序
   //2.gap==1,直接插入排序
   int gap = n;
   while (gap > 1)
   {
       gap = gap / 3 + 1;
       //+1可以保证最后一次一定是1
       for (int i = 0; i < n - gap; i++)
       {
           int end = i;
           int tmp = a[end + gap];
           while (end >= 0)
           {
               if (a[end] > tmp)
               {
                   a[end + gap] = a[end];
                   end = end - gap;
               }
               else
               {
                   break;
               }
           }
           a[end + gap] = tmp;
       }
   }
}

void BubbleSort(int* a, int n)
{
   for (int j = 0; j < n; j++)
   {
       bool exchange = false;
       for (int i = 1; i < n - j; i++)
       {
           if (a[i - 1] > a[i])
           {
               int tmp = a[i];
               a[i] = a[i - 1];
               a[i - 1] = tmp;
               exchange = true;
           }
       }
       if (exchange == false)
       {
           break;
       }
   }
}

void Swap(int* a1, int* a2)
{
   int tmp = *a1;
   *a1 = *a2;
   *a2 = tmp;
}

void SelectSort(int* a, int n)
{
   int begin = 0;
   int end = n - 1;
   while (begin < end)
   {
       int maxi = begin;
       int mini = begin;
       for (int i = begin; i <= end; i++)
       {
           if (a[i] > a[maxi])
           {
               maxi = i;
           }
           if (a[i] < a[mini])
           {
               mini = i;
           }
       }
       Swap(&a[begin], &a[mini]);
       //如果maxi和begin重叠，修正一下即可
       if (begin ==maxi)
       {
           maxi = mini;
       }
       Swap(&a[end], &a[maxi]);
       ++begin;
       --end;
   }
}

//向下调整算法
void AdjustDown(int* a, int n, int parent)
{
   //默认左孩子小
   int child = parent * 2 + 1;
   while (child < n)//孩子在数组范围内
   {
       //选出左右孩子中大的那一个
       //有可能假设错了
       //左孩子不存在，一定没有右孩子——完全二叉树
       //左孩子存在，有可能没有右孩子
       if (child + 1 < n && a[child + 1] > a[child])
           //    右孩子存在            右孩子>左孩子
           //不能这么写 if (a[child + 1] > a[chid] && child + 1 < n )
           //这样写会有越界的风险 因为是先访问了数组中的元素 再去比较右孩子是否存在
       {
           ++child;
       }
       //child就是大的那个孩子
       //不关心到底是左孩子还是右孩子
       if (a[child] > a[parent])
       {
           Swap(&a[child], &a[parent]);
           parent = child;
           child = parent * 2 + 1;//默认又算的是左孩子
       }
       else
       {
           break;
       }

   }
}
void HeapSort(int* a, int n)
{
   //建堆——向下调整建堆
   int i = 0;
   for (i = (n - 1 - 1) / 2; i >= 0; i--)
   {
       AdjustDown(a, n, i);
   }
   //升序——建大堆
   int end = n - 1;
   while (end > 0)
   {
       Swap(&a[0], &a[end]);
       AdjustDown(a, end, 0);
       --end;
   }
}

Sort.h的内容：

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<stdbool.h>
void PrintArray(int* a, int n);
// 直接插入排序
void InsertSort(int* a, int n);

// 希尔排序
void ShellSort(int* a, int n);

// 直接选择排序
void SelectSort(int* a, int n);

// 堆排序
void AdjustDown(int* a, int n, int root);
void HeapSort(int* a, int n);

// 冒泡排序
void BubbleSort(int* a, int n);

test.c的内容：

#include"Sort.h"
void TestInsertSort()
{
   int a[] = { 2,1,4,3,6,5,7,9,8,10 };
   PrintArray(a, sizeof(a) / sizeof(a[0]));
   InsertSort(a, sizeof(a) / sizeof(a[0]));
   PrintArray(a, sizeof(a) / sizeof(a[0]));
}
void TestShellSort()
{
   int a[] = { 2,1,4,3,6,5,7,9,8,10 };
   PrintArray(a, sizeof(a) / sizeof(a[0]));
   ShellSort(a, sizeof(a) / sizeof(a[0]));
   PrintArray(a, sizeof(a) / sizeof(a[0]));
}
void TestBubbleSort()
{
   int a[] = { 2,1,4,3,6,5,7,9,8,10 };
   PrintArray(a, sizeof(a) / sizeof(a[0]));
   BubbleSort(a, sizeof(a) / sizeof(a[0]));
   PrintArray(a, sizeof(a) / sizeof(a[0]));
}
void TestSelectSort()
{
   int a[] = { 2,1,4,3,6,5,7,9,8,10 };
   PrintArray(a, sizeof(a) / sizeof(a[0]));
   SelectSort(a, sizeof(a) / sizeof(a[0]));
   PrintArray(a, sizeof(a) / sizeof(a[0]));
}
void TestHeapSort()
{
   int a[] = { 2,1,4,3,6,5,7,9,8,10 };
   PrintArray(a, sizeof(a) / sizeof(a[0]));
   HeapSort(a, sizeof(a) / sizeof(a[0]));
   PrintArray(a, sizeof(a) / sizeof(a[0]));
}
// 测试排序的性能对比
void TestOP()
{
   srand(time(0));
   const int N = 100000;
   int* a1 = (int*)malloc(sizeof(int) * N);
   int* a2 = (int*)malloc(sizeof(int) * N);
   int* a3 = (int*)malloc(sizeof(int) * N);
   int* a4 = (int*)malloc(sizeof(int) * N);
   int* a5 = (int*)malloc(sizeof(int) * N);
   int* a6 = (int*)malloc(sizeof(int) * N);
   int* a7 = (int*)malloc(sizeof(int) * N);

   for (int i = 0; i < N; ++i)
   {
       a1[i] = rand();
       a2[i] = a1[i];
       a3[i] = a1[i];
       a4[i] = a1[i];
       a5[i] = a1[i];
       a6[i] = a1[i];
       a7[i] = a1[i];
   }

   int begin1 = clock();
   InsertSort(a1, N);
   int end1 = clock();

   int begin2 = clock();
   ShellSort(a2, N);
   int end2 = clock();

   int begin3 = clock();
   SelectSort(a3, N);
   int end3 = clock();

   int begin4 = clock();
   HeapSort(a4, N);
   int end4 = clock();

 

   int begin7 = clock();
   BubbleSort(a7, N);
   int end7 = clock();

   printf("InsertSort:%d\n", end1 - begin1);
   printf("ShellSort:%d\n", end2 - begin2);
   printf("SelectSort:%d\n", end3 - begin3);
   printf("HeapSort:%d\n", end4 - begin4);

   printf("BubbleSort:%d\n", end7 - begin7);

   free(a1);
   free(a2);
   free(a3);
   free(a4);
   free(a5);
   free(a6);
   free(a7);
}
   
int main()
{
   //TestInsertSort();
   //TestShellSort();
   //TestBubbleSort();
   //TestSelectSort();
   //TestHeapSort();

   TestOP();
   return 0;
}

 

好啦，小雅兰今天的学习内容就到这里结束啦，后续会继续更新快速排序和归并排序的知识点！！！