插入排序、选择排序与冒泡排序
冒泡排序冒泡排序想必各人并不陌生，其思想是利用双层循环，依次比力每个数，第一次比力前n个数，将最大的数排至最后，再比力前n-1个数，选出次大的数排至倒数第二，以此类推，将无序数组升序排列出来。
直接实现
void Swap(int* p1, int* p2)
{
int* tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
// 冒泡排序
void BubbleSort(int* a, int n)
{
for (int i = 0; i < n; i++)
{
//这里要注意j要小于n-i-1，因为比较的是a与a，要防止数组越界
for (int j = 0; j < n - i - 1; j++)
{
if (a > a)
{
Swap(&a, &a);
}
}
}
}
插入排序
插入排序与冒泡排序恰好相反，其是从左到右排至有序，冒泡则是从右至左排至有序。插入排序的思想是利用双层循环依次排挤前 i+1 个数，让前 i+1 个数有序，让第 i+1 个数与前 i 个数比力，让其排为升序或降序，接着将 i++，继续排前 i 个数，直至循环结束。
详细过程如图所示(将每步拆解画出):
https://img-blog.csdnimg.cn/direct/20127a3f522b45818acad477622c169d.png
https://img-blog.csdnimg.cn/direct/e8f1f3a76b334cbcabe56fdcbfb5a351.png
代码实现为
// 插入排序
void InsertSort(int* a, int n)
{
//防止数组越界
for (int i = 0; i < n - 1; i++)
{
int end = i;
//这里的a要注意使用i下标要小于n-1，防止越界
int tmp = a;
while (end >= 0)
{
if (tmp < a)
{
//end+1位置的值已经被记录，这里可以直接覆盖
a = a;
end--;
}
//如果tmp>=a，就不需要比较，因为前面end个数为有序，a位置为最大的值
else
{
break;
}
}
//最后把end+1原本位置的值放到合适的位置上
a = tmp;
}
} 选择排序
选择排序的思想就是，每次遍历一遍数组，第一次遍历前n个数，找出最大数的坐标，与最后一个位置的数互换，或找出最小数的坐标，与第一个位置的数互换，然后遍历前n-1或后 n-1个数，找出次大或次小的数，进行互换，以此类推。
// 选择排序
void SelectSort(int* a, int n)
{
int end = n - 1;
while (end >= 0)
{
int maxi = 0;
//每次取第一个位置的地方作为最大值的坐标进行比较，
//所以，循环从1开始，不必与自己位置的值比较
for (int i = 1; i <= end; i++)
{
if (a < a)
{
maxi = i;
}
}
Swap(&a, &a);
end--;
}
} 在此底子上，我们可以进行改进优化，每次取出最大值和最小值的坐标，然后与结尾和开头互换，再begin++、end--，缩小范围将继续找次小和次大的值。
但是优化的选择排序中就要注意一个小细节
https://img-blog.csdnimg.cn/direct/e691e19f97cb49c4856184fed2021cbc.png
按照这个代码，似乎并没有很好的实现排序，但如果细致观察，似乎是这两个位置反了导致的问题，那毕竟为什么会出问题？我们画图来表明。
https://img-blog.csdnimg.cn/direct/f943d63f951d40eca2f3f7e4add9df7d.png
以是说，细节决定成败，下面是精确的优化后的选择排序代码。
// 选择排序
void SelectSort(int* a, int n)
{
int end = n - 1, begin = 0;
while (end >= begin)
{
int maxi = begin, mini = begin;
//每次取begin位置的地方作为最大值的坐标进行比较，
//所以，循环从begin + 1开始，不必与自己位置的值比较
for (int i = begin + 1; i <= end; i++)
{
if (a < a)
{
maxi = i;
}
if (a > a)
{
mini = i;
}
}
Swap(&a, &a);
//因为先交换最大值与end位置，要注意最小值在end位置的情况
//此时最小值被换到了记录maxi的位置
if (mini == end)
{
mini = maxi;
}
Swap(&a, &a);
end--;
begin++;
}
}
// 选择排序
void SelectSort(int* a, int n)
{
int end = n - 1, begin = 0;
while (end >= begin)
{
int maxi = begin, mini = begin;
//每次取begin位置的地方作为最大值的坐标进行比较，
//所以，循环从begin + 1开始，不必与自己位置的值比较
for (int i = begin + 1; i <= end; i++)
{
if (a < a)
{
maxi = i;
}
if (a > a)
{
mini = i;
}
}
Swap(&a, &a);
//因为先交换最小值与begin位置，要注意最大值在begin位置的情况
//此时的最大值被换到记录mini的位置
if (maxi == begin)
{
maxi = mini;
}
Swap(&a, &a);
end--;
begin++;
}
} 总结加三种排序算法的比力
https://img-blog.csdnimg.cn/direct/a2d6b51265e141e18fcd9a42af23984a.png
我们可以通过一些办法来验证
这是利用C语言中的函数，随机天生100000个随机数，分别计算运行这三个排序算法所耗费的时间。
https://img-blog.csdnimg.cn/direct/94884fcb83f34211bdaf8c4b436ae569.png
可以清楚的看到，插入排序比其他两个要好很多，插入排序的适应性非常强。
总的来说，插入排序是时间复杂度为O(N^2)的排序算法中最好的一个。希尔排序就是运用了插入排序改良实现的。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]