赞
踩
常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。
插入排序是一种最简单直观的排序算法,它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。
##算法步骤
1)将第一待排序序列第一个元素看做一个有序序列,把第二个元素到最后一个元素当成是未排序序列。
2)从头到尾依次扫描未排序序列,将扫描到的每个元素插入有序序列的适当位置。(如果待插入的元素与有序序列中的某个元素相等,则将待插入元素插入到相等元素的后面。)
##实现代码
void insert_sort(int *num, int len)
{
for (int i = 1; i < len; i++)
{
int temp = num[i];
int j = i;
while (j > 0 && num[j - 1] > temp)
{
num[j] = num[j - 1];
j--;
}
num[j] = temp;
}
}
希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的:
希尔排序的基本思想是:先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录“基本有序”时,再对全体记录进行依次直接插入排序。
##算法步骤
1)选择一个增量序列t1,t2,…,tk,其中ti>tj,tk=1;
2)按增量序列个数k,对序列进行k 趟排序;
3)每趟排序,根据对应的增量ti,将待排序列分割成若干长度为m的子序列,分别对各子表进行直接插入排序。仅增量因子为1 时,整个序列作为一个表来处理,表长度即为整个序列的长度。
##实现代码1
void shell_sort(int num[], int len) { int i, j, k, group, temp; for (group = len / 2; group > 0; group /= 2) { //对每个分组进行插入排序 for (i = 0; i < group; i++) { for (j = i + group; j < len; j += group) { if (num[j - group] > num[j]) { temp = num[j]; k = j - group; while(k >= 0 && num[k] > temp) { num[k + group] = num[k]; k -= group; } num[k + group] = temp; } } } } }
##实现代码2
void shell_sort(int *num, int len)
{
for (int d = len / 2; d > 0; d /= 2)
{
//每个元素与其组内的元素进行插入排序
for (int i = d; i < len; i++
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。