排序——插入排序、希尔排序、选择排序-创新互联
目录
一.插入排序
1.实现
2.时间复杂度
二.希尔排序
2.预排序
(1).单次预排序的实现
(2).相对有序
2.代码
三.选择排序
1.实现
2.优化
一.插入排序 1.实现
正如其名，是将第n+1个数据插入到前面的n的升序（降序）数据中，形成一个n+1大小的升序（降序）序列。
由于前面的n个数据为升序，那么我们只需要将第n+1个数据依次与前n个进行比较，当比他小时便可以停止比较进行插入，无须继续与前面的数据比较。
void Swap(int* m, int* n)
{
int mid = *m;
*m = *n;
*n = mid;
}for (int j = n; j >0; j--)
{
if (a[j]< a[j - 1])
Swap(&a[j], &a[j - 1]);
else
break;
}那么，若是想要完成一段无序数组的排序，我们只需要从第二个元素开始进行插入即可（第一个元素本身就是有序的）。
void InsertSort(int* a, int n)
{
for (int i = 0; i< n-1; i++)
{
for (int j = i; j >0; j--)
{
if (a[j + 1]< a[j])
Swap(&a[j], &a[j + 1]);
else
break;
}
}
}2.时间复杂度
当每一次排序都需要末尾元素与前面每一个元素进行比较时，时间复杂度大，精确为2+3+4+5+...+n，所以最差时间复杂度为O(N^2)。
但当这个数组本身就为有序，那么这时时间复杂度最佳为O(N)（因为即使有序，我们也要遍历一遍来比较一次）。
同时，我们也可以得知，当数组接近有序时，时间复杂度会降低。
二.希尔排序
希尔排序，便是由希尔这个人提出来的，其实是插入排序的一种优化。
在上面，我们得知，当数组接近有序时，时间复杂度会降低。而这种排序，是在进行插入排序之前，通过预排序将数组变得接近有序。
2.预排序
那么什么是预排序呢？
预排序是将间隔为gap的元素分为gap组，分别进行插入排序，从而使整个数组变得相对有序。
(1).单次预排序的实现例如我们令gap=3
这样，我们便将这组数据分为了三组
其中每一组的排序和插入排序类似
for (int i = 0; i< n - gap; i += gap)
{
for (int j = i; j >= 0; j -= gap)
{
if (a[j + gap]< a[j])
Swap(&a[j], &a[j + gap]);
else
break;
}
}之后我们队每一组数据来进行排序
第一组
第二组
第三组
for(int k = 0; k< gap; k++)
{
for (int i = k; i< n-gap; i+=gap)
{
for (int j = i; j >= 0; j-=gap)
{
if (a[j + gap]< a[j])
Swap(&a[j], &a[j + gap]);
else
break;
}
}
}当然，我们没有必要真的在代码中将其分为三部分来排序，我们只需要将每一个数据与前面间隔gap的一些数据比较即可
for (int i = 0; i< n - gap; i++)
{
for (int j = i; j >= 0; j-=gap)
{
if (a[j + gap]< a[j])
Swap(&a[j], &a[j + gap]);
else
break;
}
}如此，我们便能实现一次预排序。
(2).相对有序在预排序过后，整个数组会变得相对有序
那么gap为多少时更加有序呢？
这个很容易得知，gap越大，更加相对无序，而gap越小，就更加相对有序，当gap为1时，便直接成为插入排序
因此，我们可以进行多次预排序（gap由大到小），最后进行插入排序（gap=1）
而这个gap的值，我们可以定为 n / 2，而为了进行多次预排序，我们可以每次使 gap/=2（gap/=3+1）,这样也会使得最终gap为1，从而进行插入排序。
2.代码
void ShellSort(int* a, int n)
{
int gap = n;
while (gap >1)
{
gap /= 2;
for (int i = 0; i< n - gap; i++)
{
for (int j = i; j >= 0; j-=gap)
{
if (a[j + gap]< a[j])
Swap(&a[j], &a[j + gap]);
else
break;
}
}
}
}三.选择排序 1.实现
选择排序，顾名思义，是选择出最小（大）的数字，并将其放置在最前面（最后面）。不断进行这一操作，便能完成排序。
void SelectSort(int* a, int n)
{
int min = 0;
for (int i = 0; i< n - 1; i++)
{
min = i;
for (int j = i+1; j< n; j++)
{
if (a[j]< a[min])
min = j;
}
Swap(&a[i], &a[min]);
}
}这样，我们便可以实现升序
2.优化当然，我们也可以进行一些简单的优化，我们在前面是使用将最小值交换至左侧，当然，也可以是将大值交换到右侧，而我们为了减少遍历次数，也可以选择这两种方式同时进行。
void TwoWaySelectSort(int* a, int n)
{
int min = 0;
int max = 0;
for (int i = 0; i<= n / 2; i++)
{
min = i;
max = i;
for (int j = i + 1; j< n - i; j++)
{
if (a[j]< a[min])
min = j;
if (a[j] >a[max])
max = j;
}
Swap(&a[i], &a[min]);
Swap(&a[n-i-1], &a[max]);
}
}但当我们直接以这种方式实操起来时（我们选择先交换最小值，再交换大值），会出现一些小小的问题。
例如上面的序列中，我们可以发现，max与left在同一个位置，这样会导致left位置的值被交换两次。在第一次交换后，left位置的值已经不是大值了，但还是会被当做大值与right位置的值交换。因此，为了避免类似问题的出现，我们可以在max位置的值被交换走后改变max的位置
void TwoWaySelectSort(int* a, int n)
{
int min = 0;
int max = 0;
for (int i = 0; i<= n / 2; i++)
{
min = i;
max = i;
for (int j = i + 1; j< n - i; j++)
{
if (a[j]< a[min])
min = j;
if (a[j] >a[max])
max = j;
}
Swap(&a[i], &a[min]);
//改变max位置
if (max == i)
max = min;
Swap(&a[n-i-1], &a[max]);
}
}你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
分享标题：排序——插入排序、希尔排序、选择排序-创新互联
网站地址：http://ybzwz.com/article/ejiii.html
