锐客网

  1. 首页 > 睿知 > it技术 > >

数据结构—动画表示八大排序算法

八大排序数据结构IT知识

缥帙各舒散，前后互相逾。这篇文章主要讲述数据结构—动画表示八大排序算法相关的知识，希望能为你提供帮助。


一、直接插入排序
基本思想：
我们平时玩扑克牌时，摸牌阶段的排序就用到了插入排序的思想

  • 1、当插入第n个元素时，前面的n-1个数已经有序
  • 2、用这第n个数与前面的n-1个数比较，找到要插入的位置，将其插入（原来位置上的数不会被覆盖，因为提前保存了）
  • 3、原来位置上的数据，依次后移
具体实现：
  • ①单趟的实现（将x插入到 [0,end] 的有序区间）
即一般情况下的插入，我们随机列举了一些数字，待插入的数字分为两种情况


（1）待插入的数字是在前面有序数字的中间数，直接比较将x赋值给end+1位置
（2）x是最小的一个数，end就会到达-1的位置，最后直接将x赋值给end+1位置



  • ②整个数组排序的实现
我们一开始并不知道数组是不是有序的，所以我们控制下标，end从0开始，将end+1位置的值始终保存到x中，循环进行单趟排序即可，最后结束时end=n-2，n-1位置的数字保存到x中

总体代码：
void InsertSort(int* a, int n)

assert(a);

for (int i = 0; i < n - 1; ++i)

int end = i;
int x=a[end+1]; //将end后面的值保存到x里面了
//将x插入到[0，end]的有序区间
while (end > = 0)

if (a[end] > x)

a[end + 1] = a[end]; //往后挪动一位
--end;

else

break;


a[end + 1] = x; //x放的位置都是end的后一个位置


直接插入排序总结：
  • ①元素越接近有序，直接插入排序的效率越高
  • ②时间复杂度:O(N^2)
最坏的情况下，每次插入一个数字，前面的数字都要挪动一下，一共需要挪动1+2+3+……+n=n(n+1)/2
③空间复杂度：O(1)
没有借助额外的空间，只用到常数个变量
二、希尔排序
基本思想：
  • 1、先选定个小于n的数字作为gap，所有距离为gap的数分为一组进行预排序（直接插入排序）
  • 2、再选一个小于gap的数，重复①的操作
  • 3、当gap=1时，相当于整个数组就是一组，再进行一次插入排序即可整体有序
例如：

具体实现：
①单组排序
和前面的直接插入相同，就是把原来的间隔为1，现在变为gap了，每组分别进行预排序

②多组进行排序

③整个数组进行排序（控制gap）
多次预排序（gap> 1）+ 一次插入排序（gap==1）
（1）gap越大，预排越快，越不接近于有序
（2）gap越小，预排越慢，越接近有序
结果就是：

总体代码：
void ShellSort(int* a, int n)


int gap = n;
while (gap > 1)

gap /= 2;

for (int i = 0; i < n - gap; i++)

int end = i;
int x = a[end + gap];
while (end > = 0)

if (a[end] > x)

a[end + gap] = a[end];
end -= gap;

else

break;


a[end + gap] = x;



希尔排序总结：
  • ①希尔排序是对直接插入排序的优化
  • ②时间复杂度：O(N^1.3)
  • ③空间复杂度：O(1)
三、选择排序
基本思想：
每次从数组中选出最大的或者最小的，存放在数组的最右边或者最左边，直到全部有序
具体实现：
我们这里进行了优化，一次排序中，直接同时选出最大的数（a[maxi]）和最小的数（a[mini]）放在最右边和最左边，这样排序效率是原来的2倍
  • ①单趟排序
找到最小的数字（a[mini]）和最大的数字（a[maxi]），将他们放在最左边和最右边
ps：其中的begin，end保存记录左右的下标，mini，maxi记录保存最小值和最大值得下标

  • ②整个数组排序
begin++和end–这样下次就可以排剩下的n-2个数字，再次进行单趟，如此可构成循环，直到begin小于end
整体代码：
void SelectSort(int* a, int n)

int begin = 0,end = n - 1;

while (begin< end)

int mini = begin, maxi = begin;

for (int i = begin; i < = end; i++)

if (a[i] < a[mini])

mini = i;

if (a[i] > a[maxi])

maxi = i;


Swap(& a[mini], & a[begin]);
//当begin==maxi时，最大值会被换走，修正一下
if (begin==maxi)

maxi=mini;

Swap(& a[maxi], & a[end]);
begin++;
end--;


直接选择排序总结：
  • ①直接选择排序很好理解，但实际效率不高，很少使用
  • ②时间复杂度：O(N^2)
  • ③空间复杂度：O(1)
四、堆排序 基本思想：
  • 1、将待排序的序列构造成一个大堆，根据大堆的性质，当前堆的根节点（堆顶）就是序列中最大的元素；
  • 2、将堆顶元素和最后一个元素交换，然后将剩下的节点重新构造成一个大堆；
  • 3、重复步骤2，如此反复，从第一次构建大堆开始，每一次构建，我们都能获得一个序列的最大值，然后把它放到大堆的尾部。最后，就得到一个有序的序列了。
  • 小结论：
    排升序，建大堆
    排降序，建小堆
具体实现：、
  • ①向下调整算法
我们将给定的数组序列，建成一个大堆，建堆从根节点开始就需要多次的向下调整算法


堆的向下调整算法（使用前提）：
（1）若想将其调整为小堆，那么根结点的左右子树必须都为小堆。
（2）若想将其调整为大堆，那么根结点的左右子树必须都为大堆。



向下调整算法的基本思想：
  • 1、从根节点开始，选出左右孩子值较大的一个
  • 2、如果选出的孩子的值大于父亲的值，那么就交换两者的值
  • 3、将大的孩子看做新的父亲，继续向下调整，直到调整到叶子节点为止
//向下调整算法
//以建大堆为例
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 ])//如果这里右孩子存在，
//且更大，那么默认较大的孩子就改为右孩子

child++;

if(a[child]> a[parent])

Swap(& a[child], & a[parent]);
parent = child;
child = parent * 2 + 1;

else

break;



  • ②建堆（将给定的任意数组建成大堆）


建堆思想：
从倒数第一个非叶子节点开始，从后往前，依次将其作为父亲，依次向下调整，一直调整到根的位置
【数据结构—动画表示八大排序算法】

    推荐阅读


    上一篇：第一个SSM整个框架完成增删改查的项目（里面的配置文件可以复用）

    下一篇：没有了