桂林网上服务_建行网站_百度seo费用_seo具体怎么优化

实际中我们玩扑克牌时，就用了插入排序的思想

当插入第 i(i>=1) 个元素时，前面的 array[0],array[1],…,array[i-1] 已经排好序，此时用 array[i] 的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将 array[i] 插入，原来位置上的元素顺序后移

动图演示：

代码示例：

void InsertSort(int* a, int n)
{//[0,end]有序，插入tmp依旧有序for (int i = 1; i < n; i++){int end = i - 1;int tmp = a[i];while (end >= 0){if (a[end] > tmp){a[end + 1] = a[end];end--;}else{break;}}a[end + 1] = tmp;}
}

如果从头开始比较的话，我们想象一下摸牌的过程，当我们摸了第一张牌的时候，那么这张牌就是有序的，摸第二张牌的时候要跟第一张牌进行比较，如果小就放在前面，比它大就放在后面。摸第三张牌就跟第二张进行比较，以此类推，摸第n张牌就跟第n-1张进行比较。其中第一张牌就是end，要摸的牌就是tmp，依次比较就要end--，我们要以计算机的思路进行比较，实际生活中我们一眼就能看出牌应该在哪个位置。OK,这就是插入排序的逻辑思路了。

2.2.2 希尔排序

至于gap取多少后面我们会来进行讨论。我们先来看一下第一组排序是怎样实现的

这样看是不是跟插入排序有点相似。我们继续来看红色的这一组是怎样实现的

红色这一组排完就看其它组该怎样排序该如何实现？在套一组循环就OK了

不过代码还能继续优化，可以多组并排，如下图

我们来看一下2种方式的区别

接下来我们来看当gap取不同的值时，它们的预排序是什么结果

将区间按照基准值划分为左右两半部分的常见方式有：

1.hoare版本

动图演示：

hoare版本有2个问题，一个是死循环（遇到重复出现的值）另一个是越界。

死循环的解决办法就是加等号，越界的问题就要判断left是否小于right

上面只是第一次排序的过程，还要进行递归才能排完序

代码示例：

int PartSort1(int* a, int left, int right)
{int keyi = left;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和leftreturn left;
}

void QuickSort(int* a, int begin, int end)
{if (begin > end)return;int keyi = PartSort1(a, begin, end);//int keyi = PartSort2(a, begin, end);//int keyi = PartSort3(a, begin, end);QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);
}

这里面有些问题需要注意，如何保证相遇位置就一定比key小

2.挖坑法

动图示例：

挖坑法比较好理解，就不用过多解释了

代码示例：

//挖坑法
int PartSort2(int* a, int left, int right)
{int key = a[left];int hole = left;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;return hole;
}

3.前后指针法

动图演示：

思想：1.最开始prev和cur是相邻的。

2.当cur遇到比key大的值以后，它们之间的值都是比key大的值

3.cur找小，找到小的以后，先++prev，然后交换prev的位置和cur的位置，相当于把大的翻滚式往右边推的同时把小的换到左边

代码示例：

int PartSort3(int* a, int left, int right)
{int prev = left;int cur = left + 1;int keyi = left;while (cur <= right){if (a[cur] < a[keyi] && ++prev != cur){Swap(&a[prev], &a[cur]);}++cur;}Swap(&a[prev], &a[keyi]);keyi = prev;return keyi;
}

快速排序优化：

每次选key都是中位数，效率就很好。当数据有序的时候，变成最坏，时间复杂度是O(N^2)。

解决方法是1.随机数选key     2.三数取中

三数取中代码

//三数取中
int GetMidIndex(int* a, int left, int right)
{int mid = (left + right) / 2;if (a[left] < a[mid]){if (a[mid] < a[right])return mid;else if (a[left] < a[right])return right;elsereturn left;}else{if (a[mid] > a[right])return mid;else if (a[left] > a[right])return right;elsereturn left;}
}

然后再三个版本中加入这2行代码

2.3.4 快速排序的非递归实现

void QuickSortNonR(int* a, int begin, int end)
{ST st;STInit(&st);STPush(&st,end);STPush(&st,begin);while (!STEmpty(&st)){int left = STTop(&st);STPop(&st);int right = STTop(&st);STPop(&st);int keyi = PartSort1(a, left, right);// [left, keyi-1] keyi [keyi+1, right]if (keyi + 1 < right){STPush(&st, right);STPush(&st, keyi+1);}if (left < keyi - 1){STPush(&st, keyi - 1);STPush(&st, left);}}STDestroy(&st);
}

2.3.5 各种排序算法的比较

我们可以用10万个数据来看一看这几种排序的时间差异，看一下哪种算法好

void TestOP()
{srand(time(0));const int N = 100000;int* a1 = (int*)malloc(sizeof(int) * N);int* a2 = (int*)malloc(sizeof(int) * N);int* a3 = (int*)malloc(sizeof(int) * N);int* a4 = (int*)malloc(sizeof(int) * N);int* a5 = (int*)malloc(sizeof(int) * N);int* a6 = (int*)malloc(sizeof(int) * N);int* a7 = (int*)malloc(sizeof(int) * N);for (int i = 0; i < N; ++i){a1[i] = rand();a2[i] = a1[i];a3[i] = a1[i];a4[i] = a1[i];a5[i] = a1[i];a6[i] = a1[i];a7[i] = a1[i];}int begin1 = clock();InsertSort(a1, N);int end1 = clock();int begin2 = clock();ShellSort(a2, N);int end2 = clock();int begin3 = clock();BubbleSort(a3, N);int end3 = clock();int begin4 = clock();SelectSort(a4, N);int end4 = clock();int begin5 = clock();HeapSort(a5, N);int end5 = clock();int begin6 = clock();QuickSort(a6, 0, N - 1);int end6 = clock();printf("InsertSort:%d\n", end1 - begin1);printf("ShellSort:%d\n", end2 - begin2);printf("BubbleSort:%d\n", end3 - begin3);printf("SelcetSort:%d\n", end4 - begin4);printf("HeapSort:%d\n", end5 - begin5);printf("QuickSort:%d\n", end6 - begin6);free(a1);free(a2);free(a3);free(a4);free(a5);free(a6);free(a7);
}

2.4 归并排序

2.4.1概念

• 分割：将待排序的序列不断地⼆分为两个⼦序列，直到每个⼦序列只剩下⼀个元素。
• 归并：将两个有序⼦序列合并为⼀个有序序列。

2.4.2 基本思想

2.4.3 非递归实现方式

void MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);int gap = 1;while (gap < n){int j = 0;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;if (end1 >= n || begin2 >= n){break;}// 修正if (end2 >= n){end2 = n - 1;}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));}gap *= 2;}free(tmp);
}

2.3.4 递归方式实现

void _MergeSort(int* a,int begin, int end,int* tmp)
{if (begin == end)return;int mid = (begin + end) / 2;// [begin, mid] [mid+1, end]_MergeSort(a, begin, mid, tmp);_MergeSort(a, mid+1, end, tmp);int begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;int i = begin;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 + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}void MergeSort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);_MergeSort(a, 0, n - 1, tmp);free(tmp);
}

1. 非递归方式实现的空间复杂度更低：递归⽅式需要使⽤系统栈来保存函数调⽤信息，当递归深度较大时，可能会导致栈溢出。而非递归⽅式可以使⽤循环和迭代来实现，不需要使⽤额外的空间，因此空间复杂度更低。
2. 非递归方式实现的效率更⾼：递归⽅式需要频繁地进行函数调⽤和返回操作，每次调⽤和返回都会带来额外的开销。而非递归方式只需要进⾏简单的循环和迭代，效率更高。
3. ⾮递归方式实现的代码更易于理解和调试：递归方式实现的代码⽐较难以理解和调试，因为递归过程中函数的调⽤顺序⽐较复杂。而非递归方式实现的代码结构更加清晰，易于理解和调试。