数据结构排序合集（笔记）
目录
一.插入排序与希尔排序
时间复杂度 空间复杂度 稳定性 插入排序 O（N^2） O(1) 稳定 希尔排序 O(N^1.3) O(1) 不稳定
插入排序：
希尔排序（两个排序的时间复杂度是一样的，即使是四循环，他们效率也相同）：
二.选择排序与堆排序
时间复杂度 空间复杂度 稳定性 选择排序 O(N^2) O(1) 不稳定 堆排序 O(N*logN) O(1) 不稳定
void SelectSort(int* a, int n)//选择排序
{
int begin = 0;
int end = n - 1;
while(begin < end)
{
int mini = begin;
int maxi = end;
for (int i = begin; i <= end; i++)//选出最大和最小进行交换
{
if (a[i] < a[mini])
{
mini = i;
}
if (a[i] > a[maxi])
{
maxi = i;
}
}
swap(&a[mini], &a[begin]);
if (begin == maxi)
maxi = mini;
swap(&a[maxi], &a[end]);
end--;
begin++;
}
}（选择排序是特别慢，也没有稳定性的排序，可能连冒泡都比不过）
堆排序（ 因为要排升序，所以建大堆）：
三.冒泡排序和快速排序
时间复杂度 空间复杂度 稳定性 冒泡排序 O(N^2) O(1) 稳定 快速排序 O(N*logN) O(logN)~O(N) 不稳定
冒泡排序：
快速排序：
int Getmid(int*a,int left,int right)//三数取中
{
int midi = (left + right) / 2;
if (a[right] > a[left])
{
if (a[midi] > a[right])
{
return right;
}
else if (a[midi] < a[left])
{
return left;
}
else
return midi;
}
else// if (a[left] >= a[right])
{
if (a[midi] > a[left])
{
return left;
}
else if (a[midi] < a[right])
{
return right;
}
else
return midi;
}
}
不用使用递归的qsort（用堆去模拟递归）
void QuickSortNonR(int* a, int left, int right)
{
Stack st;
StackInit(&st);
StackPush(&st, right);
StackPush(&st, left);
while (!StackEmpty(&st))
{
int begin = StackTop(&st);
StackPop(&st);
int end = StackTop(&st);
StackPop(&st);
int keyi = PartSort3(a, begin, end);
if (keyi + 1 < end)
{
StackPush(&st, end);
StackPush(&st, keyi + 1);
}
if (begin < keyi - 1)
{
StackPush(&st, keyi - 1);
StackPush(&st, begin);
}
}
StackDestroy(&st);
}四.归并排序
时间复杂度 空间复杂度 稳定性 归并排序 O(N*logN) O(logN) 稳定
void _MergeSort(int* a, int* tmp, int left,int right)
{
if (left >= right)
return;
int midi = (left + right) / 2;
_MergeSort(a, tmp, left, midi);
_MergeSort(a, tmp, midi+1, right);
//归
int begin1 = left, end1 = midi;
int begin2 = midi+1, end2 = right;
int i = left;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] <= a[begin2])
{
tmp[i++] = a[begin1++];
}
else
{
tmp[i++] = a[begin2++];
}
}
while (begin1 <= end1)
{
tmp[i++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[i++] = a[begin2++];
}
memcpy(a+left, tmp+left, sizeof(int)*((right - left)+1));
}非递归实现归并排序：
void MergeSortNonR(int* a, int n)
{
int* tmp = (int*)malloc(n*sizeof(int));
if (tmp == NULL)
{
perror("malloc fail");
return;
}
int gap = 1;
while (gap < n)
{
for (int i = 0; i < n;i += 2*gap)//
{
int begin1 = i, end1 = i + gap - 1;
int begin2 = i + gap, end2 = i + 2 * gap - 1;
int j = i;
//[i,end1] [i+gap,end2]
if (begin2 >= n)
break;
if (end2 >= n)
end2 = n-1;
printf("[%d %d] [%d %d]", begin1, end1, begin2, end2);
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] <= a[begin2])
{
tmp[j++] = a[begin1++];
}
else
{
tmp[j++] = a[begin2++];
}
}
while (begin1 <= end1)
{
tmp[j++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[j++] = a[begin2++];
}
memcpy(a+i, tmp+i, sizeof(int) * (end2 - i +1));//
}
printf("\n");
gap = 2*gap;
}
free(tmp);
tmp = NULL;
}五.计数排序
// 计数排序
void CountSort(int* a, int n)
{
int max = a[0], min = a[0];
for (int i = 0; i < n; i++)//选出最大最小得到区间大小
{
if (max < a[i])
max = a[i];
if (min > a[i])
min = a[i];
}
int range = max - min +1 ;
int* count = (int*)calloc(range,sizeof(int));
if (count == NULL)
{
perror("malloc fail");
return;
}
for (int i = 0; i < n; i++)//给新数组进行计数
{
count[a[i] - min]++;
}
int j = 0;
for (int i = 0; i < range; i++)//覆盖旧数组
{
while (count[i]--)
{
a[j++] = i + min;
}
}
free(count);
count = NULL;
}原文地址：https://blog.csdn.net/be_a_big_cattle/article/details/140585761
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！