归并排序
递归
基本思想：
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。先递归，再排序
1.把数组从中间俩边分开进行递归进行分解
2.分解为最小后进行排序，分为左边和右边，将左边和右边的值想比较，最小的先放入tmp数组，之后把大的放入
3.把左边或右边剩余的未拷贝的拷贝到tmp数组中
4.把tmp数组中的数据拷贝回原数组
void _MergeSort(int* a, int begin, int end, int* tmp) { if (begin >= end) return; int mid = (begin + end) / 2; _MergeSort(a, begin, mid, tmp); _MergeSort(a, mid+1, end, tmp); int begin1 = begin; int end1 = mid; int i = begin1; int begin2 = mid + 1; int end2 = end; 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, ((end - begin) + 1) * sizeof(int)); } void MergeSort(int* a, int n) { int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == NULL) return; _MergeSort(a, 0, n - 1, tmp); free(tmp); } void PrintArray(int* a, int n) { for (int i = 0; i < n; i++) printf("%d ", a[i]); printf("\n"); } int main() { int a[8] = {10,6,7,1,3,9,4,2 }; MergeSort(a,8); PrintArray(a, 8); return 0; }
非递归
先1个2个归，然后再2个2个归，再4个4个归，这里要重新设置begin1 end1 begin2 end2
因为随着gap的变化这四个变量的范围也有所变化，每归一轮结束后，gap要乘2，当gap>=n时，结束循环
void PrintArray(int* a, int n) { for (int i = 0; i < n; i++) printf("%d ", a[i]); printf("\n"); } void _MergeSort1(int* a, int n) { int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == NULL) return; int gap = 1; while (gap < n) { for (int i = 0; i < n; i = i + 2 * gap) { int begin1 = i; int end1 = i + gap - 1; int begin2 = i + gap; int end2 = i + 2 * gap - 1; int j = begin1; 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, tmp, n * sizeof(int)); gap = gap * 2; } PrintArray(a, 8); } void MergeSort1(int* a, int n) { _MergeSort1(a, n); } int main() { int a[8] = {10,6,7,1,3,9,4,2 }; MergeSort1(a,8); return 0; }
但是这样写会出问题，当数组内数字个数不是2的整数次幂的时候，就会发生越界
9个数据和10个数据等都会发生越界，而越界的数字是end1,begin2,end2，为了防止越界，我们可把上面越界情况写出来end1 >= n，begin2 >= n，end2 >= n ，而在程序中如果要进入循环应执行以下语句
while (begin1 <= end1 && begin2 <= end2)
begin1<=end1,begin2<=end2才进入循环，根据这个循环，我们判断如果end1>=n,begin2>=n,end2>=n时，我们可将他们的范围修改，使其不进入循环或进入循环后没影响，对end1>=，我们可让end1=n-1,这样让其进入循环，但对结果也不会产生影响，如上面的[8,11]，我们设置为[8,8]这样它归并后只会出去一个数字8，然后随便修正begin2和end2，使begin2<end2，就行因为后面后有俩个while，所以不用担心有数字没归到
加入下面循环语句‘
if(end1>=n) { end1=n-1; begin2=n; end2=n-1; } else if(begin2>=n) { begin2=n; end2=n-1; } else if(end2>=n) { end2=n-1; } void PrintArray(int* a, int n) { for (int i = 0; i < n; i++) printf("%d ", a[i]); printf("\n"); } void _MergeSort1(int* a, int n) { int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == NULL) return; int gap = 1; while (gap < n) { for (int i = 0; i < n; i = i + 2 * gap) { int begin1 = i; int end1 = i + gap - 1; int begin2 = i + gap; int end2 = i + 2 * gap - 1; int j = begin1; if (end1 >= n) { end1 = n - 1; begin2 = n; end2 = n - 1; } else if (begin2 >= n) { begin2 = n; end2 = n - 1; } else 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, tmp, n * sizeof(int)); gap = gap * 2; } PrintArray(a, 10); } void MergeSort1(int* a, int n) { _MergeSort1(a, n); } int main() { int a[10] = {10,6,7,1,3,9,4,2,10,11 }; MergeSort1(a,10); return 0; }
修正后的边界
这样不管对几个都可以进行排序，不存在越界问题
另一种写法，当越界的时候，我们就不归了，但是要归并一次就要拷贝一次
void MergeSortNonR(int* a, int n) { int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == NULL) { printf("malloc fail\n"); exit(-1); } int gap = 1; while (gap < n) { //printf("gap=%d->", gap); for (int i = 0; i < n; i += 2 * gap) { // [i,i+gap-1][i+gap, i+2*gap-1] int begin1 = i, end1 = i + gap - 1; int begin2 = i + gap, end2 = i + 2 * gap - 1; // end1越界或者begin2越界，则可以不归并了 if (end1 >= n || begin2 >= n) { break; } else if (end2 >= n) { end2 = n - 1; } //printf("[%d,%d] [%d, %d]--", begin1, end1, begin2, end2); int m = end2 - begin1 + 1; int j = begin1; 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) * m); } gap *= 2; } free(tmp); }
非比较排序
非比较排序有桶排序，计数排序，基数排序
计数排序
计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。 操作步骤：
1. 统计相同元素出现次数
2. 根据统计的结果将序列回收到原来的序列中
0出现2次，1出现0次，2出现2次，3出现3次，4出现0次，5出现1次
每个数出现几次相对应的位置就++几次
然后再写回原数组
局限性：1.如果是浮点数，字符串就无法用这种方法
2.如果数据范围很大，空间复杂度就会很高，相对不适合
如果数组是：1000，1005，1000，1008，1009，1006
不可能开1000多个数据不然比较浪费，此时就要使用绝对映射
使用相对映射：1000-0
1001-1
……
1009-9
这样即使有负数，也能进行排序
-5对应0
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) 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) { //出现几次，回写几个i+min while (count[i]--) { a[j++] = i + min; } } } int main() { int a[10] = {10,6,7,1,3,9,4,2,10,11 }; CountSort(a,10); return 0; }
时间复杂度：O(max（range，N）)
空间复杂度：O(range)
