一、冒泡排序
1、步骤
左边大于右边交换一趟排下来最大的在右边
2、思路
动图演示如下：
3、代码实现
void BubbleSort(int* a, int n) { int exchange = 0; for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - 1 - i; j++) { if (a[j] > a[j + 1]) { Swap(&a[j], &a[j + 1]); exchange = 1; } } if (exchange == 0) { break; } } }
4、特性总结
1、时间复杂度：O（N^2）
2、空间复杂度O（1）
3、稳定性：稳定
5、实现结果
二、快速排序
1、步骤
任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
2、思路
hoare版（左右指针法）
挖坑法
前后指针法
3、代码实现
三数取中对代码进行优化
void GetMid(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])//mid最大 { return right; } else { return left; } } //a[left] > a[mid] else { if (a[mid] > a[right]) { return mid; } else if (a[left] > a[right])//mid最小 { return right; } else { return left; } } }
快排优化
减少递归调用函数开辟的空间
void QuickSort(int* a, int begin, int end) { if (begin >= end) return; if (end - begin + 1 > 10) { int keyi = PartSort3(a, begin, end); QuickSort(a, begin, keyi - 1); QuickSort(a, keyi + 1, end); } else { Insertsort(a + begin, end - begin + 1); } }
hoare（左右指针法）
//hoare版 int PartSort1(int* a, int left, int right) { int midi = GetMidi(a, left, right); Swap(&a[midi], &a[left]); 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]); return left; } void QuickSort(int* a, int begin, int end) { if (begin >= end) return; if (end - begin + 1 > 10) { int keyi = PartSort3(a, begin, end); QuickSort(a, begin, keyi - 1); QuickSort(a, keyi + 1, end); } else { Insertsort(a + begin, end - begin + 1); } }
挖坑法
//挖坑法 int PartSort2(int* a, int left, int right) { int midi = GetMidi(a, left, right); Swap(&a[midi], &a[left]); 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 left; } void QuickSort(int* a, int begin, int end) { if (begin >= end) return; if (end - begin + 1 > 10) { int keyi = PartSort3(a, begin, end); QuickSort(a, begin, keyi - 1); QuickSort(a, keyi + 1, end); } else { Insertsort(a + begin, end - begin + 1); } }
前后指针法
//前后指针法 int PartSort3(int* a, int left, int right) { int midi = GetMidi(a, left, right); Swap(&a[midi], &a[left]); int keyi = left; int prev = left; int cur = left + 1; while (cur <= right) { if (a[cur] < a[keyi]&& prev++ != cur) { Swap(&a[cur], &a[prev]); } ++cur; } Swap(&a[keyi], &a[prev]); return prev; } void QuickSort(int* a, int begin, int end) { if (begin >= end) return; if (end - begin + 1 > 10) { int keyi = PartSort3(a, begin, end); QuickSort(a, begin, keyi - 1); QuickSort(a, keyi + 1, end); } else { Insertsort(a + begin, end - begin + 1); } }
非递归实现
借助栈实现
//快排非递归 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); if (keyi + 1 < right) { STPush(&st, right); STPush(&st, keyi+1); } if (left<keyi-1) { STPush(&st, keyi-1); STPush(&st, left); } } STDestroy(&st); }
4、特性总结
1、时间复杂度：O（N*logN）
2、空间复杂度：O（logN）
3、稳定性：不稳定 例如：5 0 5 7 10 5 8
5、实现结果
三、归并排序
1、步骤
分解：将待排序的数组不断分成两个子数组，直到每个子数组只有一个元素为止。
合并：将相邻的两个子数组合并成一个有序数组，直到最后只剩下一个有序数组为止
2、思路
动图演示如下：
3、代码实现
递归实现
void _MergeSort(int* a, int* tmp, int begin, int end) { if (end <= begin) return; int mid = (end + begin) / 2; _MergeSort(a, tmp, begin, mid); _MergeSort(a, tmp, mid + 1, end); int begin1 = begin, end1 = mid; int begin2 = mid + 1, end2 = end; int index = begin; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] < a[begin2]) { tmp[index++] = a[begin1++]; } else { tmp[index++] = a[begin2++]; } } while (begin1 <= end1) { tmp[index++] = a[begin1++]; } while (begin2 <= end2) { tmp[index++] = a[begin2++]; } memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int)); } void MergeSort(int* a, int n) { int* tmp = (int*)malloc(sizeof(int) * n); _MergeSort(a, tmp, 0, n - 1); free(tmp); }
非递归实现
void MergeSortNonR(int* a, int n) { int* tmp = (int*)malloc(sizeof(int) * n); 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; if (end2 >= n) { end2 = n - 1; } if (end1 >= n && begin2 >= n) { break; } int index = i; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] < a[begin2]) { tmp[index++] = a[begin1++]; } else { tmp[index++] = a[begin2++]; } } while (begin1 <= end1) { tmp[index++] = a[begin1++]; } while (begin2 <= end2) { tmp[index++] = a[begin2++]; } memcpy(a + i, tmp + i, (end2-i+1) * sizeof(int)); } gap *= 2; } free(tmp); }
4、特性总结
时间复杂度：O（N*logN）
空间复杂度：O（N）
稳定性：稳定
5、实现结果
四、计数排序
1、步骤
1、统计相同元素出现次数
2、根据统计的结果将序列回收到原数组中
2、思路
动图演示如下：
3、代码实现
void CountSort(int* a, int n) { int min = a[0], max = a[0]; for (int i = 0; i < n; i++) { if (a[i] < min) min = a[i]; if (a[i] > max) max = a[i]; } int range = max - min + 1; int* count = (int*)malloc(sizeof(int) * range); if (count == NULL) { perror("malloc fail"); return; } memset(count, 0, sizeof(int) * range); // 统计数据出现次数 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; } } }
4、特性总结
1、时间复杂度：O（N+range）
2、空间复杂度：O（range）
3、稳定性：稳定
5、实现结果
