排序

复杂度分析

插入排序

1.基本思想

把待排序的记录按其大小逐个插入到一个已经排序好的有序序列中，直到所有的记录插入完为止，从而得到一个有序序列。

2. 过程

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

3.特性总结

元素集合越接近有序，直接插入排序算法的时间效率越高时间复杂度：O(N^2)空间复杂度：O(1)，它是一种稳定的排序算法稳定性：稳定 适合：数据量小，接近有序

4.实现

void InsertSort(int *array,int size) { for (int i = 1; i < size; i++) { int key = array[i]; //寻找key的插入位置 int end = i - 1; while(key < array[end]) { array[end + 1] = array[end]; end--; } array[end + 1] = key; } } void SortTest() { int a[] = { 8,4,6,7,1,3,9,}; InserSort(a,sizeof(a)/sizeof(a[0])); }

希尔排序

1.基本思想

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个 组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工 作。当到达=1时，所有记录在统一组内排好序。

2.过程

3.总结

希尔排序是对直接插入排序的优化。当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就 会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。希尔排序的时间复杂度不好计算，需要进行推导，推导出来平均时间复杂度： O(N^1.3—N2）稳定性：不稳定 适合数据量大，不接近有序

4.实现

void ShellSort(int *array, int size) { int gap = 3; while (gap > 0) { for (int i = gap; i < size; ++i) { //待插入元素 int key = array[i]; //找key的插入位置： int end = i - gap; while (end >= 0 && key < array[end]) { array[end + gap] = array[end]; end = end - gap; } array[end + gap] = key; } gap--; } } void SortTest() { int a[] = { 8,4,6,7,1,3,9,}; ShellSort(a,sizeof(a)/sizeof(a[0])); }

3.选择排序

1.基本思想

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的 数据元素排完

2.过程

3.总结

直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用时间复杂度：O(N^2)空间复杂度：O(1)稳定性：不稳定 适合数据量大，数据重复量大

4.实现

void SelectSort(int *array, int size) { for (int i = 0; i < size - 1; i++)//趟数 { int MaxPos = 0; for (int j = 1; j < size - i; ++j)//找到最大值的下标 { if (array[j] > array[MaxPos]) { MaxPos = j; } } if (MaxPos != size - 1 - i) Swap(&array[MaxPos], &array[size - 1 - i]); } } //双向同时找最大最小 void SelectSortOP(int *array, int size) { int begin = 0; int end = size - 1; while (begin < end) { int MaxPos = begin; int MinPos = begin; int index = begin + 1; while (index <= end)//找到最大最小数的下标 { if (array[index] > array[MaxPos]) MaxPos = index; if (array[index] < array[MinPos]) MinPos = index; index = index + 1; } if (MaxPos != end) Swap(&array[MaxPos], &array[end]); if ( MinPos == end) //如果最小数是最后一个，再上一步交换后最小数已经交换到最大数的下标处 { MinPos = MaxPos; } if (MinPos != begin) Swap(&array[MinPos], &array[begin]); begin++; end--; } } void SortTest() { int a[] = { 8,4,6,7,1,3,9,}; SelectSort(a,sizeof(a)/sizeof(a[0])); //SelectSortOP(a,sizeof(a)/sizeof(a[0])); }

快速排序（递归）

1.基本思想

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中 的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右 子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。 将区间按照基准值划分为左右两半部分的常见方式有：

hoare版本 2. 前后指针版本 3. 挖坑法 int Partion(int *array,int left,int right) { int begin = left; int end = right - 1; int key = array[right - 1]; while (begin < end) { //从左往右找比基准值大的元素，找到之后停止 while (begin < end && array[begin] <= key) begin++; //从右往左找比基准值小的元素，找到之后停止 while (begin < end && array[end] >= key) end--; if (begin != end) Swap(&array[begin], &array[end]); } if (begin != right -1) Swap(&array[begin], &array[right - 1]);//把基准值换到中间 return begin; } int Partion1(int *array, int left, int right) { int cur = left; int pre = cur - 1; int key = array[right - 1]; while (cur < right) { if (array[cur] < key && ++pre != cur) Swap(&array[pre], &array[cur]); cur++; } if (++pre != right) { Swap(&array[pre], &array[right - 1]); } return pre; } int Partion2(int *array, int left, int right) { int begin = left; int end = right - 1; int key = array[right - 1]; while (begin < end) { //从前往后找比基准值大的元素，找到后填充end位置 while (begin < end && array[begin] <= key) { begin++; } //填充end的位置 if (begin < end) { array[end] = array[begin]; end--; } //从后往前找比基准值小的元素，找到后填充begin的位置 while (begin < end && array[end] >= key) { end--; } if (begin < end) { array[begin] = array[end]; begin++; } } array[begin] = key; return begin; } void QuickSort(int* array, int left, int right) { // if (right - left > 1) // { // int div = Partion2(array, left, right);//Partion Partion2 // QuickSort(array, left, div); // QuickSort(array, div + 1, right); // } if (right - left < 16) { InsertSort(array, right - left); } else { int div = Partion1(array, left, right);//Partion Partion2 QuickSort(array, left, div); QuickSort(array, div + 1, right); } }

快速排序（栈模拟递归）

导入头文件Stack.h,代码 ： https://blog.csdn.net/a331683772/article/details/90238944

void QuickSortNor(int *array, int size) { int left = 0; int right = size; Stack s; StackInit(&s); StackPush(&s, right); StackPush(&s, left); while (!StackEmpty(&s)) { left = StackTop(&s); StackPop(&s); right = StackTop(&s); StackPop(&s); int div = Partion2(array, left, right); //保存右半部分区间 StackPush(&s, right); StackPush(&s, div + 1); //保存左半部分区间 StackPush(&s, div); StackPush(&s, left); } } void SortTest() { int a[] = { 8,4,6,7,1,3,9,}; QuickSortNor(a, (sizeof(a) / sizeof(a[0]))); }

归并排序

1.基本思想

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有 序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

void MergeData(int* array, int left, int mid, int right, int* temp) { int begin1 = left, end1 = mid; int begin2 = mid, end2 = right; int index = left; while (begin1 < end1 && begin2 < end2) { if (array[begin1] < array[begin2]) temp[index++] = array[begin1++]; else temp[index++] = array[begin2++]; } while (begin1 < end1) temp[index++] = array[begin1++]; while (begin2 < end2) temp[index++] = array[begin2++]; } void _MergeSort(int* array, int left, int right, int* temp) { if (right - left > 1) { int mid = left + ((right - left) >> 1); // [left, mid) // [mid, right) _MergeSort(array, left, mid, temp); _MergeSort(array, mid, right, temp); MergeData(array, left, mid, right, temp); memcpy(array+left, temp+left, sizeof(int)*(right-left)); } } void MergeSort(int* array, int size) { int* temp = (int*)malloc(sizeof(int)*size); if (NULL == temp) { assert(0); return; } _MergeSort(array, 0, size, temp); free(temp); } void MergeSortNor(int* array, int size) { int* temp = (int*)malloc(sizeof(int)*size); if (NULL == temp) { assert(0); return; } int gap = 1; while (gap < size) { for (int i = 0; i < size; i += 2 * gap) { int left = i; int mid = left + gap; int right = mid + gap; if (mid >= size) mid = size; if (right >= size) right = size; MergeData(array, left, mid, right, temp); } memcpy(array, temp, sizeof(int)*size); gap *= 2; } free(temp); }

堆排序

void HeadAdjust(int *array, int size, int root) { int child = root * 2 + 1; while (child < size) { if ((child + 1) < size && array[child] < array[child + 1]) { child = child + 1; } if (array[child] > array[root]) { Swap(&array[child], &array[root]); root = child; child = child * 2 + 1; } else { return; } } } void HeadSort(int *array, int size) { int root = (size - 2) / 2; for (; root >= 0; --root) HeadAdjust(array, size, root); int end = size - 1; while (end) { Swap(&array[0], &array[end]); HeadAdjust(array, end, 0); end--; } }