七大排序思想

目录

七大排序的时间复杂度和稳定性

排序

插入排序

简单插入排序

希尔排序

选择排序

简单选择排序

堆排序

交换排序

冒泡排序

快速排序

快排的递归实现 

hoare版本的快排

 挖坑法的快排

双指针法的快排

快排的非递归

归并排序

归并的递归实现

归并的非递归实现

补充

快排的三路划分

---

七大排序的时间复杂度和稳定性

排序时间的复杂度和稳定性-CSDN博客关于七大排序的时间复杂度和稳定性的总结，帮助读者迅速掌握各各排序的优劣，在不同情况下如何选择。https://blog.csdn.net/2401_87944878/article/details/145404375

排序

排序就是将一组数据按照递增或递减的方式将其排列。

排序包含两种；

内部排序：数据元素全部放在内存中的排序。

外部排序：数据太多不能同时放在内存中，根据排序的过程不能在内外存之间移动的排序。外部排序要对文件进行操作。

排序包含有四大实现：插入排序，选择排序，交换排序，归并排序。根据这四个实现又可以分支出一共7个排序思想：简单插入排序，希尔排序；选择排序，堆排序；冒泡排序，快速排序；归并排序。下面我们对这七种排序进行讲解。

---

插入排序

插入排序包含两种：简单插入排序，希尔排序。

简单插入排序

如图，简单插入怕排序就是遍历原数组，将每一个元素放在其指定位置。先拿出一个元素，向前找看，比它大的先后移，直到找到比它小的。

//简单插入排序
void InsertSort(int* a, int n)
{//插入排序，向前找到元素的指定位置for (int i = 1; i < n; i++){int end = i;int cur = a[end];while(end>0){if (a[end - 1] > cur){a[end] = a[end - 1];end--;}elsebreak;}a[end] = cur;}
}

希尔排序

 希尔排序实际上是对简单插入排序的一种优化。简单插入排序每次与其相邻的元素进行比较，而希尔排序是将一个数组分成多个组，将每个组进行简单插入排序，这样可以让大的数迅速到前面去，小的数迅速到后面去。

可以看到第一次gap是5时，将下标0和5比较，1和6比较，2和7比较....这样可以迅速将大的数移到前面去，将小的数移到后面去，这样就使的数组更加趋于有序的状态。

通过gap从大到小的变化，使得当gap较小的时候可以快速向前找到它的位置，更快的让每次循环break掉，让效率更快。

//希尔排序
void ShellSort(int* a, int n)
{//希尔排序与插入排序的区别在于，其先进行预排序int gap = n;while (gap > 1){gap /= 2;for (int i = 0; i < gap; i++){for (int m = i + gap; m < n; m += gap){int end = m;int cur = a[end];while (end > 0){if (a[end - 1] > cur){a[end] = a[end - 1];end--;}elsebreak;}a[end] = cur;}}}
}

---

选择排序

选择排序包含两种简单选择排序和堆排序；

简单选择排序

简单选择排序就是遍历原数组，直接找到最大值或最小值将其放在尾和首，可以一次只找出一个最值，也可以将最大值和最小值同时找到。

以上是遍历未排序的数组每次找出最下的元素交换，下面演示遍历未排序的数组每次找打最小和最大的元素。 

//交换函数
void Swap(int* a, int* b)
{int tmp = *a;*a = *b;*b = tmp;
}//简单选择排序
void SelectSort(int* a, int n)
{//一次遍历，选出最大值和最小值int left = 0;int right = n - 1;while (left < right){int min = left;int max = left;for (int i = left; i <= right; i++){if (a[min] > a[i])min = i;if (a[max] < a[i])max = i;}//交换Swap(&a[left], &a[min]);//注意此处，如果left对应的值就是最大值的时候，//将min和left交换后，max就在min的位置了if (left == max)Swap(&a[right], &a[min]);elseSwap(&a[right], &a[max]);left++, right--;}
}

堆排序

堆排序就是利用二叉树的性质，通过建大堆或小堆，将最大的数据或最小的数据放在指定位置。在二叉树中已经详细讲过堆了，这里就直接贴代码。

二叉树（C语言）-CSDN博客文章浏览阅读1.3k次，点赞19次，收藏18次。帮助读者快速掌握树这一数据结构，了解堆的功能，能够实现堆排序，以及如何再大量数据中快速找到前K个最大元素，如何处理普通二叉树，普通二叉树的遍历等知识。https://blog.csdn.net/2401_87944878/article/details/145262931https://blog.csdn.net/2401_87944878/article/details/145262931https://blog.csdn.net/2401_87944878/article/details/145262931https://blog.csdn.net/2401_87944878/article/details/145262931https://blog.csdn.net/2401_87944878/article/details/145262931https://blog.csdn.net/2401_87944878/article/details/145262931

//向下调整
void AdjustDown(int* a, int n, int parent)
{int child = 2 * parent + 1;while (child < n){if (child+1<n&&a[child] < a[child + 1])child++;if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = 2 * parent + 1;}elsebreak;}
}//堆排序
void HeapSort(int* a, int n)
{//先建大堆for (int i = (n - 2) / 2; i >= 0; i--){//向下调整AdjustDown(a, n, i);}//将堆顶的最大值和堆低交换int sz = n - 1;Swap(&a[0], &a[sz]);sz--;while (sz > 0){AdjustDown(a, sz + 1, 0);Swap(&a[0], &a[sz]);sz--;}
}

---

交换排序

交换排序分为冒泡排序和快速排序。

冒泡排序

冒泡排序简单，没有实际作用，这里直接贴代码。

//冒泡排序
void BubbleSort(int* a, int n)
{for (int i = 0; i < n - 1; i++){for (int m = 0; m < n - 1 - i; m++){if (a[m] > a[m + 1])Swap(&a[m], &a[m + 1]);}}
}

快速排序

快速排序是将一个元素key作为基准，先找到这个key的准确位置，将小于key的放在key的左边，将大于key的放在右边。

快排的递归实现 

hoare版本的快排

 如图：将数组首元素作为key，通过左右指针，让R指针先走找到小于key的值停，L指针再走大于key的时候停，将L位置和R位置交换，直到L和R相遇时停止，这个位置就是key排序后的位置。

思考：为什么要让R指针想走？能否让L指针想走？ 

关于key的选择有三种方法：选择最左边的，随机选择，比较数组左右中间这三个值，选出次小的值。此处选择三数取中最好，可以尽量避免只出现一个递归函数。

//快排：Hoare版本
void QuickSort(int* a, int begin,int end)
{if (begin >= end)return;//快排就是将key放在正确位置上去。//三数取中int mid = Mid(begin, end);Swap(&a[begin], &a[mid]);int keyi = begin;int left = begin;int right = end;while (left < right){while (left < right && a[right] >= a[keyi])right--;while (left < right && a[left] <= a[keyi])left++;Swap(&a[left], &a[right]);}Swap(&a[keyi], &a[left]);keyi = left;QuickSort(a, begin, keyi - 1);QuickSort(a, keyi+1, end);
}

 挖坑法的快排

利用挖坑法可以直接不用思考数组那一边的指针先走的问题。

挖坑法就是将keyi的位置值保留，R指针找比key小的将其填在keyi的位置，R指针处变为坑，直到L指针和R指针相遇，将其位置的key填入坑。

//快排：挖坑法
void HoleSort(int* a, int begin, int end)
{if (begin >= end)return;int mid = Mid(begin, end);Swap(&a[mid], &a[begin]);int hole = begin;int left = begin;int right = end;int key = a[hole];while (left < right){while (left < right && a[right] >= key)right--;a[hole] = a[right];hole = right;while (left < right && a[left] <= key)left++;a[hole] = a[left];hole = left;}a[hole] = key;int keyi = hole;HoleSort(a, 0, keyi - 1);HoleSort(a, keyi+1, end);
}

双指针法的快排

分别利用两个指针，一个向前面走如果cur对用的值比key小就交换，两个指针都向前移动；如果cur对应的值大就不交换，cur向前移动。

//快排：双指针法
void DPoint(int* a, int begin, int end)
{if (begin >= end)return;int mid = Mid(begin, end);Swap(&a[begin], &a[mid]);int keyi = begin;int cur = begin;int pre = begin;while (cur <= end){if (a[cur] <= a[keyi]){if (cur != pre)Swap(&a[cur], &a[pre]);cur++;pre++;}else{cur++;}}Swap(&a[keyi], &a[pre - 1]);keyi = pre - 1;DPoint(a, begin, keyi - 1);DPoint(a, keyi+1, end);
}

---

快排的非递归

快排的非递归就是利用栈将其begin和end的值储存起来，再利用栈的“后入先出”的性质，每一次拿出一个范围再放入子范围，直到栈的空间为空时停止。

此处以Hoare的非递归为例。

typedef struct Stack
{int* a;int size;int capacity;
}Stack;//栈的初始化
void StackInit(Stack* sp)
{sp->capacity = 4;sp->a = (int*)malloc(sizeof(int) * (sp->capacity));if (sp->a == NULL)perror("malloc failed");sp->size = 0;
}//入栈
void StackPush(Stack* sp, int x)
{//检查空间够不够if (sp->size == sp->capacity){sp->capacity *= 2;int* tmp = (int*)realloc(sp->a, sizeof(int) * (sp->capacity));if (tmp == NULL)perror("realloc failed");sp->a = tmp;}sp->a[sp->size] = x;sp->size++;
}//出栈
void StackPop(Stack* sp)
{sp->size--;
}//返回栈顶元素
int StackTop(Stack* sp)
{return sp->a[sp->size - 1];
}//检查栈空间是否为空
bool IsStackEmpty(Stack* sp)
{if (sp->size == 0)return true;elsereturn false;
}

//快排：非递归
void QuickNon(int* a, int begin, int end)
{//快排的非递归就是将快排的左右间距存储在栈中Stack s;StackInit(&s);StackPush(&s, end);StackPush(&s, begin);while (!IsStackEmpty(&s)){int begin = StackTop(&s);StackPop(&s);int end = StackTop(&s);StackPop(&s);int left = begin;int keyi = left;int right = end;while (left < right){while (left < right && a[right] >= a[keyi])right--;while (left < right && a[left] <= a[keyi])left++;Swap(&a[left], &a[right]);}Swap(&a[left], &a[keyi]);keyi = left;if (begin < keyi - 1){StackPush(&s, keyi - 1);StackPush(&s, begin);}if (keyi + 1 < end){StackPush(&s, end);StackPush(&s, keyi + 1);}}
}

---

归并排序

归并排序的实现就是：先对小范围排序，再对大范围排序。如图：相对两个元素进行排序，再对4个元素进行排序，依次依次*2向后排序。

归并的递归实现

//归并排序
void Merge(int* a, int begin, int end)
{if (begin >= end)return;int mid = (begin + end) / 2;Merge(a, begin, mid);Merge(a, mid + 1, end);int begin1 = begin;int end1 = mid;int begin2 = mid + 1;int end2 = end;int* tmp = (int*)malloc(sizeof(int) * (end - begin + 1));int j = 0;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[j++] = a[begin1++];}elsetmp[j++] = a[begin2++];}while (begin1 <= end1)tmp[j++] = a[begin1++];while (begin2 <= end2)tmp[j++] = a[begin2++];memcpy(a + begin, tmp, sizeof(int) * (end - begin + 1));free(tmp);
}

归并的非递归实现

归并的非递归实现就不能用栈来存储18首尾的范围了，可以直接从2个元素排序开始，依次*2直到排完为止。

//归并的非递归实现
void MergeNon(int* a, int begin, int end)
{int gap = 1;while (gap < end){for (int i = 0; i <= end; i += 2 * gap){int begin1 = i;int end1 = i + gap - 1;int begin2 = i + gap;int end2 = i + 2 * gap - 1;if (begin2 > end){break;}if (end2 > end)end2 = end;int* tmp = (int*)malloc(sizeof(int) * (end2 - begin1 + 1));int j = 0;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2])tmp[j++] = a[begin1++];elsetmp[j++] = a[begin2++];}while (begin1 <= end1)tmp[j++] = a[begin1++];while (begin2 <= end2)tmp[j++] = a[begin2++];memcpy(a + i, tmp, sizeof(int) * (end2-i+1));free(tmp);}gap *= 2;}
}

---

补充

关于快排，当有大量重复的数据出现的时候，快排的key的位置可能就是最左边，导致向下递归后还是只有一组，当大量出现这种情况的时候就会导致快排变成简单选择排序，时间复杂度大大增加，导致效率降低。此处可以采用三路划分的快排解决。

快排的三路划分

三路划分与普通快排的区别：普通快排将数组分成两个部分，大于key和小于key的；而三路划分将快排分成三个部分，大于key，小于key和等于key的。

分为左右两个指针以及一个遍历数组的指针，将大于key的调到右边，将小于key的调到左边，将等于key的放在中间。

//快排的三路划分
void TQuickSort(int* a, int begin, int end)
{if (begin >= end)return;int mid = Mid(begin, end);Swap(&a[begin], &a[mid]);int keyi = begin;int key = a[begin];int left = begin;int cur = begin;int right = end;while (cur <= right){if (a[cur] < key){if (cur != left)Swap(&a[left], &a[cur]);left++, cur++;}else if (a[cur] > key){Swap(&a[cur], &a[right]);right--;}elsecur++;}keyi = left;TQuickSort(a, begin, keyi - 1);TQuickSort(a, keyi + 1, end);
}