13:57:09 2019-08
学习
16:56:35 2019-08-24
补充了插值查找
排序算法:起泡排序 归并排序(二路归并)
1 #define _CRT_SECURE_NO_WARNINGS //vs中scanf为不安全的函数 要使用 得加上这句话 2 #include<stdio.h> 3 #include<malloc.h> 4 #define Size 10 5 int Vector[Size] = { 1,8,5,64,54,32,15,96,12,3 }; 6 void Swap(int i, int j) //交换下表为i j的两个元素 7 { 8 int temp = Vector[i]; 9 Vector[i] = Vector[j]; 10 Vector[j] = temp; 11 } 12 //排序算法 13 //起泡排序 最好O(n) 最坏O(n^2) 14 /*void BubbleSort() 15 { 16 for (int i = 0; i < Size; i++) 17 { 18 int IsSwap = 0; //判断是否经过交换 19 for (int j = 0; j < Size-i-1; j++) 20 { 21 if (Vector[j] > Vector[j + 1]) 22 { 23 Swap(j, j + 1); 24 IsSwap = 1; 25 } 26 } 27 if (!IsSwap) 28 return; 29 } 30 }*/ 31 //邓公的写法 32 /*int Bubble(int lo, int hi) 33 { 34 int IsSwap = 0; //判断是否经过交换 35 while (++lo<hi) 36 { 37 if (Vector[lo-1] > Vector[lo]) 38 { 39 Swap(lo - 1, lo); 40 IsSwap = 1; 41 } 42 } 43 return IsSwap; 44 } 45 void BubbleSort(int lo,int hi) 46 { 47 while (Bubble(lo,hi--)); 48 }*/ 49 //再改进 50 int Bubble(int lo, int hi) 51 { 52 int LastPosition = 0; //最后交换的位置 53 while (++lo < hi) 54 { 55 if (Vector[lo - 1] > Vector[lo]) 56 { 57 Swap(lo - 1, lo); 58 LastPosition = lo; 59 } 60 } 61 return LastPosition; //返回最后交换的位置 62 } 63 void BubbleSort(int lo, int hi) 64 { 65 while (lo<(hi=Bubble(lo, hi))); //将hi置为最后交换的位置 用lo来判断可以少一步进入函数 66 } 67 68 //归并排序 //O(nlogN) 69 //二路归并 70 /*void Merge(int lo, int mi, int hi) //归并 71 { 72 int a[20] = { 0 }; //栈上申请空间 存放排序后的向量元素 73 int i = 0; 74 int low = lo; 75 int mid = mi; 76 while (low<mi||mid<hi) 77 { 78 if (low<mi&&(mid>=hi||Vector[low] < Vector[mid])) //当mid>=hi时 右边已经没有元素了 这时候直接添加就可以 或者左边首元素小于右边首元素这时候也直接添加 79 a[i++] = Vector[low++]; //再者一定要保证low小于mi 因为在这个过程中(如果不加这个条件) low会超出 导致某一个元素比较2次 80 else if(mid<hi&&(low>=mi||Vector[mid]<=Vector[low])) 81 a[i++] = Vector[mid++]; 82 } 83 for (int i = lo; i < hi; i++) //将排好序的元素写回 84 { 85 Vector[i] = a[i - lo]; 86 } 87 }*/ 88 //邓公的二路归并做法 //当然 邓公用的是c++ 这里是c的实现方法 89 void Merge(int lo, int mi, int hi) //O(n) //邓公的做法是只为左边元素申请空间 对元素比对后的结果直接覆盖原数组 90 { //经过分析 这样做是对的 因为不管怎么做 右边的元素总不会被覆盖掉 始终保持着有效性 91 int* A = Vector + lo; //声明一个指向 左边向量首元素的指针 92 int* B = (int*)malloc(sizeof(int) * (mi - lo)); //申请一块空间来存放左边元素 93 for (int i = 0; i < mi - lo; B[i] = A[i++]); //存放左边元素 94 int* C = Vector + mi; //声明一个指向 右边向量首元素的指针 95 /*for (int i = 0, j = 0, k = 0;j<mi-lo||k<hi-mi;) // i用于A j用于B k用于C 96 { 97 if ((j < mi - lo) && (k >= hi - mi || B[j] <=C[k]))A[i++] = B[j++]; 98 if ((k < hi - mi) && (j >= mi - lo || C[k] <B[j]))A[i++] = C[k++]; //这部分思想是相同的 99 }*/ 100 //简化后 当j到了末尾 其实已经做完了 排序工作 101 for (int i = 0, j = 0, k = 0; j < mi - lo /*|| k < hi - mi*/;) // i用于A j用于B k用于C 102 { 103 if (/*(j < mi - lo) && */k >= hi - mi || B[j] <=C[k])A[i++] = B[j++]; 104 if ((k < hi - mi) && /*(j >= mi - lo ||*/ C[k] < B[j])A[i++] = C[k++]; //这部分思想是相同的 105 } 106 free(B); 107 } 108 109 void MergeSort(int lo, int hi) //排序 [lo,hi) 110 { 111 if (hi - lo < 2)return; //单元素自然有序 112 int mi = (hi + lo) >> 1; //取数组中点为界 113 MergeSort(lo, mi); //对前半部分排序 114 MergeSort(mi, hi); //对后半部分排序 115 Merge(lo, mi, hi); //归并 116 } 117 118 int main() 119 { 120 MergeSort(0,Size); 121 for (int i = 0; i < Size; i++) 122 printf("%d ", Vector[i]); 123 printf(" "); 124 }
邓公讲的太好了 不能听现场真遗憾