标签：inf 使用 没有 情况 代码 实现 void 循环 为什么
一.直接（选择）插入排序
有两种方式：升序和降序 我使用升序
第一种排序：直接（简单）插入排序：每次向已经排序好的
队列里面找个合适的位置，将值插入
//笔试和面试：
//1.算法的描述 2.算法的实现 3.效率（时间复杂度和空间复杂度和稳定性）
//稳定性定义：如果两个关键值A和A`,如果一开始A就在A`前面，你排序后A还在A`前面，我们就认为
是稳定的
//怎么看稳定性：看有没有跳跃交换
//第一种排序算法：直接插入排序：如果数组基本有序，我们就用直接插入排序，越有序，时间复杂度
越小，极端情况下为O（n）
//时间复杂度O（n^2） 空间复杂度O（1） ，稳定的
//为什么不用从前向后找：如果数组有序，则时间复杂度太大
具体代码实现：
#include
#include
void InsertSort(int arr[], int len)
{
//循环多少次 个数-1
//用临时量tmp保存关键值，从后向前找，比它小的或者走到了头，就将关键值放到下一个位置上
assert(arr != NULL);
if (NULL == arr)
return;
int count = 0;
int tmp = 0;
int j = 0;
for (int i = 1; i //控制揭牌后需要排序的次数
{
tmp = arr[i];
for (j = i - 1; j >= 0; j--)//从后向前找
{
if (arr[j] > tmp)//比关键值大，则向后移动
{
arr[j + 1] = arr[j];
count++;
}
else
{
break;//找到了比它小的值 退出
}
}
arr[j + 1] = tmp;
}
printf("count %d\n", count);
}
void Show(int* arr, int len)
{
assert(arr != NULL);
if (NULL == arr)
return;
for (int i = 0; i )
{
printf("%d ", arr[i]);
}
printf("\n");
}
int main()
{
int arr[] = { 2,4,6,8,23,98,76,56,74,36,1,3,5,7,99,66,77,88 };
InsertSort(arr, sizeof(arr) / sizeof(arr[0]));
Show(arr, sizeof(arr) / sizeof(arr[0]));
return 0;
}
第二种排序算法：希尔shell排序，就是一种特殊的直接插
入排序，只不过调用了很多次直接插入排序，//按增量分组
要求：增量最后一个必须为1， 增量保持互素
希尔排序效率分析：
1.时间复杂度O（n^1.3~1.5）
2.空间复杂度O(1)
3.稳定性：发生了跳跃交换，所以不稳定
不稳定
例如：
分成5组，处理之后的值：
分成3组，处理之后的值：
最后分成1组，处理之后的值：
具体代码实现：
#include
#include
static void Shell(int arr[], int len, int gap)//gap 分成多少组（间隔）
{
int tmp = 0;
int j = 0;
int count = 0;
for (int i = gap; i //i开始的位置
{
tmp = arr[i];
for (j = i - gap; j >= 0; j = j - gap)
{
if (arr[j] > tmp)
{
arr[j + gap] = arr[j];
count++;
}
else
{
break;
}
}
arr[j + gap] = tmp;
}
printf("%d count %d\n", gap, count);
}
void ShellSort(int arr[], int len)
{
assert(arr != nullptr);
if (NULL == arr)
return;
int dk[] = { 5, 3, 1 };
for (int i = 0; i sizeof(dk) / sizeof(dk[0]); i++)
{
Shell(arr, len, dk[i]);
}
}
void Show(int* arr, int len)
{
assert(arr != NULL);
if (NULL == arr)
return;
for (int i = 0; i )
{
printf("%d ", arr[i]);
}
printf("\n");
}
int main()
{
int arr2[] = { 2,4,6,8,23,98,76,56,74,36,1,3,5,7,99,66,77,88 };
ShellSort(arr2, sizeof(arr2) / sizeof(arr2[0]));
Show(arr2, sizeof(arr2) / sizeof(arr2[0]));
return 0;
}
八种排序方法
标签：inf 使用 没有 情况 代码 实现 void 循环 为什么
原文地址：https://www.cnblogs.com/xpei-1124/p/14786322.html
