【数据结构】常见的7种比较排序算法1

● 直接插入排序（Insert Sort）

1、算法描述：

? ??该算法是一种简单直观的是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上只需用到O(1)的额外空间的排序，因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位为最新元素提供插入空间。

2、步骤：

1）从第一个元素开始，该元素可以认为已经被排序

2）取出下一个元素，在已经排序的元素序列中从后向前扫描

3）如果该元素（已排序）大于新元素，将该元素移到下一位置

4）重复步骤3，直到找到已排序的元素小于或者等于新元素的位置

5）将新元素插入到该位置中

6）重复步骤2?

? ? 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率，但插入排序一般来说是低效的， 因为插入排序每次只能将数据移动一位。

具体实现如下：

void?InsertSort(int?*arr,?size_t?size)//直接插入排序
{
?assert(arr);
?for?(size_t?i?=?0;?i?<?size?-?1;?++i)
?{
??int?end?=?i;
??int?tmp?=?arr[i?+?1];//tmp取出要插入的元素(下一个元素)
??while?(end?>=?0?&&?arr[end]?>?tmp)//end要大于等于0
??{
???arr[end?+?1]?=?arr[end];//大于tmp的数后移
???--end;
??}
??arr[end?+?1]?=?tmp;
?}
}

● 希尔排序（Shell Sort）

1、算法描述：

? ? 希尔排序，也称递减增量排序算法，是插入排序的一种高速而稳定的改进版本。希尔排序是基于插入排序而提出改进方法的。设置增量为gap=size/3+1,在gap不为1时，希尔排序是在进行预排序，在gap==1时，进行插入排序时，可提高效率。

1）设置增量gap为size

2）使gap=gap/3+1，同时对所有组进行插入排序，直到size-gap-1时，表示所有组已经排序完成

3）重复步骤2，直到gap为1时停止

具体实现如下：

void?ShellSort(int?*arr,?size_t?size)//希尔排序
{
?assert(arr);
?int?gap?=?size;//gap设置插入排序区间
?while?(gap?>?1)
?{
??gap?=?gap?/?3?+?1;//防止gap为2时，下一次gap为1，使得最后一次的gap为1
??//例如（2?5?4?9?3?6?8?7?1）使多组同时进行直接插入排序
??for?(size_t?i?=?0;?i?<?size?-?gap;?++i)
??{
???int?end?=?i;
???int?tmp?=?arr[i?+?gap];
???while?(end?>=?0?&&?arr[end]?>?tmp)
???{
????arr[end?+?gap]?=?arr[end];
????end?-=?gap;
???}
???arr[end?+?gap]?=?tmp;
??}
?}
}

● 选择排序（Select Sort）1、算法描述：

? ? 首先在未排序序列中找到最小和最大元素，存放到排序序列的两端，然后，再从剩余未排序元素中继续寻找最小和最大元素，然后放到排序序列（该序列缩短了2个元素，不包含原序列的两端）两端。以此类推，直到所有元素均排序完毕。

1）一重循环：通过i和size控制进行寻找最小和最大元素的区间

2）使min为区间的首位元素位置，max为区间的末尾元素位置

3） 二重循环：从序列中寻找最小和最大元素，注意在进行不断比较过程中进行交换，不能在找到的它们的下标后才进行交换。

具体实现如下：

void?SelectSort(int?*arr,?size_t?size)
{
?int?min,?max;
?for?(size_t?i?=?0;?i?<?size;?++i,?--size)
?{
??min?=?i;
??max?=?size?-?1;//max为当前选择排序段的最后一个数据
??//max?=?size?-?1?-?i时：注意不能用size进行减1，防止max=size-i-i中size的改变，重新定义len进行变化
??for?(int?j?=?i;?j?<=?max;?++j)
??{
???if?(arr[j]?<?arr[min])
???{
????swap(arr[j],?arr[min]);
???}
???if?(arr[j]?>?arr[max])
???{
????swap(arr[j],?arr[max]);
???}
??}
?}
}

● 堆排序（Heap Sort）

? ??堆积排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

? ? 升序序列的实现需要建立大堆，降序序列的实现需要建立小堆。下面对升序序列的实现进行分析。

1）大堆的建立：通过下调建立大堆，先比较左右子结点的大小，使child指向较大数，再比较父亲结点的child所指数据的大小，小于孩子结点就进行交换。

2）每次使堆的左右子树为大堆，故从下向上进行大堆的建立

3）交换堆顶元素的堆的最后一个元素，然后重新使堆（不包含最后一个元素）成为大堆

4）重复步骤3，直到堆中只有一个元素为止

具体实现如下：

void?AdjustDown(int*?arr,?size_t?parent,?size_t?size)//建大堆（每次选出最大的放在后面）
{
?size_t?child?=?2?*?parent?+?1;
?while?(child?<?size)
?{
??if?(child?+?1?<?size?&&?arr[child?+?1]?>?arr[child])
??{
???++child;
??}
??if?(arr[child]?>?arr[parent])
??{
???swap(arr[child],?arr[parent]);
???parent?=?child;
???child?=?2?*?parent?+?1;
??}
??else
??{
???break;
??}
?}
}
void?HeapSort(int?*arr,?size_t?size)//升序（大堆），降序（小堆）
{
?assert(arr);
?for?(int?i?=?(size?-?2)?/?2;?i?>=?0;?--i)//注意边界条件，i>=0和i=(size-2)/2
?{
??AdjustDown(arr,?i,?size);
?}
?for?(size_t?i?=?0;?i?<?size;?++i)
?{
??swap(arr[0],?arr[size?-?1?-?i]);//交换，使大数放在堆的最后
??AdjustDown(arr,?0,?size?-?1?-?i);
?}
}

● 冒泡排序（Bubble Sort）

? ? 重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误（升序的）就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换（flag==0），也就是说该数列已经排序完成。该算法是越小的元素会经由交换慢慢“浮”到数列的顶端。

1）设置标志flag。

2）从开始第一对到结尾的最后一对，比较相邻的元素。如果第一个比第二个大，就交换他们两个。

3）如果flag==0，则在进行一趟比较后没有发生交换，则序列已经有序了。

4）持续每次对越来越少的元素重复步骤2、3，总共进行了size-1趟。

具体实现如下：

void?BubbleSort(int?*arr,?size_t?size)//冒泡排序，依次将大数据存放在后面
{
?assert(arr);
?int?flag?=?0;//标志位判断数组是否接近有序
?for?(size_t?i?=?0;?i?<?size?-?1;?++i)//进行了size-1趟冒泡
?{
??for?(size_t?j?=?0;?j?<?size?-?i?-?1;?++j)//进行比较，交换
??{
???if?(arr[j]?>?arr[j?+?1])
???{
????swap(arr[j],?arr[j?+?1]);
????flag?=?1;
???}
??}
??if?(flag?==?0)//一趟结束后没有一次交换，跳出循环
??{
???break;
??}
?}
}

（编辑：ASP站长网）