外排序是不是基本排序算法
基本的排序算法分为内排序和外排序，内排序：数据在内存中存储。外排序：数据在外存中存储。在本篇博客中，我们重点来细说下内排序。
内排序分为五大类，基本的有八种：
一、插入排序。
1）、直接插入排序。
算法：将待排序的数组分为两大部分，已排序部分和待排序部分，每次从待排序部分拿出一个元素，在已排序部分找到合适的位置插入元素。
以如下数组为例{12,15,9,20,6,31,24}，红线左边为已排序序列，右边为待排序序列，蓝色方框标识从待排序序列拿出来的元素。
代码实现如下：
void Insertsort(int *arr,int len)
{
int tmp=0;
int j=0;
for(int i=1;i<len ;i++)
{
tmp=arr[i];
for(j=i-1;j>=0&&arr[j]>tmp;j--)
{
arr[j+1]=arr[j];
}
arr[j+1]=tmp;
}
}
登录后复制

时间复杂度分析：
（1）顺序排列时，只需比较(n-1)次，插入排序时间复杂度为O(n)；
（2）逆序排序时，需比较n(n-1)/2次，插入排序时间复杂度为O(n^2)；
（3）当原始序列杂乱无序时，平均时间复杂度为O(n^2)。
空间复杂度分析：
插入排序过程中，需要一个临时变量temp存储待排序元素，因此空间复杂度为O(1)。
算法稳定性分析：
插入排序是一种稳定的排序算法。
2）、希尔（shell）排序。
算法：先将 整个待排序的元素序列分割成若干子序列，分别进行直接插入排序待整个序列中的元素“基本有序”后，再对全体元素进行直接插入排序。
以如下数组为例{232,4,25,16,67,87,1,54,34}：
（1）、先将数组按间隔4个元素分为若干子序列，每种颜色代表一个子序列。
（2）、对每个子序列进行直接插入排序，再按间隔为3个元素分成若干子序列。
（3）、对每个子序列进行直接插入排序，再按间隔为2个元素分成若干个子序列。
（4）、对每个子序列进行直接插入排序，再按间隔为1个元素分成若干个子序列。
（5）、最后再对整个序列进行直接插入排序。
代码如下：
void shell(int *arr,int len,int dk)
{
int i=dk;
int j=i-dk;
int tmp=0;
for(i;i<len;i++)
{
tmp=arr[i];
for(j=i-dk;j>=0&&arr[j]>tmp;j-=dk)
{
arr[j+dk]=arr[j];
}
arr[j+dk]=tmp;
}
}
void shellsort(int *arr,int len,int *dk,int dlen)
{
for(int i=0;i<dlen;i++)
{
Hill(arr,len,dk[i]);
}
}
int main()
{
int arr[]={232,4,25,16,67,87,1,54,34};
int len = sizeof(arr)/sizeof(arr[0]);
int dk[]={5,3,1};
int dlen=sizeof(dk)/sizeof(dk[0]);
shellsort(arr,len,dk,dlen);
return 0;
}
登录后复制

时间复杂度分析：
1）、增量序列的选择
shell排序的执行时间依赖于增量序列。
好的增量序列的共同特征：
① 最后一个增量必须为1；
② 应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。
有人通过大量的实验，给出了较好的结果：当n较大时，比较和移动的次数约在nl.25到1.6n1.25之间。
2）、Shell排序的时间性能优于直接插入排序
希尔排序的时间性能优于直接插入排序的原因：
①当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。
②当n值较小时，n和 n^2 的差别也较小，即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度O(n^2)差别不大。
③在希尔排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量di逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按di-1作为距离排过序，使文件较接近于有序状态，所以新的一趟排序过程也较快。
因此，希尔排序在效率上较直接插入排序有较大的改进。
内排序分为五大类，基本的有八种：
一、插入排序。
1）、直接插入排序。
算法：将待排序的数组分为两大部分，已排序部分和待排序部分，每次从待排序部分拿出一个元素，在已排序部分找到合适的位置插入元素。
以如下数组为例{12,15,9,20,6,31,24}，红线左边为已排序序列，右边为待排序序列，蓝色方框标识从待排序序列拿出来的元素。
代码实现如下：
void Insertsort(int *arr,int len)
{
int tmp=0;
int j=0;
for(int i=1;i<len ;i++)
{
tmp=arr[i];
for(j=i-1;j>=0&&arr[j]>tmp;j--)
{
arr[j+1]=arr[j];
}
arr[j+1]=tmp;
}
}
登录后复制

时间复杂度分析：
（1）顺序排列时，只需比较(n-1)次，插入排序时间复杂度为O(n)；
（2）逆序排序时，需比较n(n-1)/2次，插入排序时间复杂度为O(n^2)；
（3）当原始序列杂乱无序时，平均时间复杂度为O(n^2)。
空间复杂度分析：
插入排序过程中，需要一个临时变量temp存储待排序元素，因此空间复杂度为O(1)。
算法稳定性分析：
插入排序是一种稳定的排序算法。
2）、希尔（shell）排序。
算法：先将 整个待排序的元素序列分割成若干子序列，分别进行直接插入排序待整个序列中的元素“基本有序”后，再对全体元素进行直接插入排序。
以如下数组为例{232,4,25,16,67,87,1,54,34}：
（1）、先将数组按间隔4个元素分为若干子序列，每种颜色代表一个子序列。
（2）、对每个子序列进行直接插入排序，再按间隔为3个元素分成若干子序列。
（3）、对每个子序列进行直接插入排序，再按间隔为2个元素分成若干个子序列。
（4）、对每个子序列进行直接插入排序，再按间隔为1个元素分成若干个子序列。
（5）、最后再对整个序列进行直接插入排序。
代码如下：
void shell(int *arr,int len,int dk)
{
int i=dk;
int j=i-dk;
int tmp=0;
for(i;i<len;i++)
{
tmp=arr[i];
for(j=i-dk;j>=0&&arr[j]>tmp;j-=dk)
{
arr[j+dk]=arr[j];
}
arr[j+dk]=tmp;
}
}
void shellsort(int *arr,int len,int *dk,int dlen)
{
for(int i=0;i<dlen;i++)
{
Hill(arr,len,dk[i]);
}
}
int main()
{
int arr[]={232,4,25,16,67,87,1,54,34};
int len = sizeof(arr)/sizeof(arr[0]);
int dk[]={5,3,1};
int dlen=sizeof(dk)/sizeof(dk[0]);
shellsort(arr,len,dk,dlen);
return 0;
}
登录后复制

时间复杂度分析：
1）、增量序列的选择
shell排序的执行时间依赖于增量序列。
好的增量序列的共同特征：
① 最后一个增量必须为1；
② 应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。
有人通过大量的实验，给出了较好的结果：当n较大时，比较和移动的次数约在nl.25到1.6n1.25之间。
2）、Shell排序的时间性能优于直接插入排序
希尔排序的时间性能优于直接插入排序的原因：
①当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。
②当n值较小时，n和 n^2 的差别也较小，即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度O(n^2)差别不大。
③在希尔排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量di逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按di-1作为距离排过序，使文件较接近于有序状态，所以新的一趟排序过程也较快。
因此，希尔排序在效率上较直接插入排序有较大的改进。
外排序不是基本排序算法
外排序是指能够处理极大量数据的排序算法。通常来说，外排序处理的数据不能一次装入内存，只能放在读写较慢的外存储器（通常是硬盘）上。外排序通常采用的是一种“排序-归并”的策略。在排序阶段，先读入能放在内存中的数据量，将其排序输出到一个临时文件，依此进行，将待排序数据组织为多个有序的临时文件。尔后在归并阶段将这些临时文件组合为一个大的有序文件，也即排序结果。
基本排序算法是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。
外排序是指能够处理极大量数据的排序算法。通常来说，外排序处理的数据不能一次装入内存，只能放在读写较慢的外存储器（通常是硬盘）上。外排序通常采用的是一种“排序-归并”的策略。在排序阶段，先读入能放在内存中的数据量，将其排序输出到一个临时文件，依此进行，将待排序数据组织为多个有序的临时文件。尔后在归并阶段将这些临时文件组合为一个大的有序文件，也即排序结果。
基本排序算法是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。