Open JunYearPrisoner opened 4 years ago
JunYearPrisoner
commented
4 years ago 【选择排序】
看图：https://www.runoob.com/wp-content/uploads/2019/03/selectionSort.gif
工作原理：遍历数组，找最大值放在末尾，找最小值放在开头。
int a[len];
//省略了数组初始化以及数据的读入
for (i = 0 ; i < len - 1 ; i++){
int min = i;
for (j = i + 1; j < len; j++){
if (a[j] < a[min]) //找目前最小值
min = j;
}
swap(a[min], a[i]); //交换两个值
}
JunYearPrisoner
commented
4 years ago 【插入排序】 看图：https://www.runoob.com/wp-content/uploads/2019/03/insertionSort.gif 工作原理：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。
int arr[len];
for(int i=1;i<len;i++){
int key=arr[i];
int j=i-1;
while((j>=0) && (key<arr[j])){
arr[j+1]=arr[j];
j--;
}
arr[j+1]=key;
}
JunYearPrisoner
commented
4 years ago 【稳定性】 选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法。 冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法。 稳定性通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。在简单形式化一下，如果Ai = Aj, Ai原来在位置前，排序后Ai还是要在Aj位置前。 稳定性的好处：排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，第一个键排序的结果可以为第二个键排序所用。基数排序就 是这样，先按低位排序，逐次按高位排序，低位相同的元素其顺序再高位也相同时是不会改变的。（百度百科） https://www.cnblogs.com/tigerson/p/7156648.html
JunYearPrisoner
commented
4 years ago 【归并排序】 看图：https://www.runoob.com/wp-content/uploads/2019/03/mergeSort.gif 工作原理：分治法（会单列的）的一个典型应用。将一个大数组持续分成若干个小数组，小数组可以看成已经排完序的数组。然后将小数组合并排序到大数组中。所以该算法有三点：分解，排序，合并。难在最后一步合并，合并时要分别比较两个小数组中的数的大小，两个数组数可能不一样多，如果一个数组的数已经用完，那么该轮循环就可以停止，不用再排，这时用一个特殊值来表达数组结束，遇见那个特殊值不用再进行比较直接把剩下的另一个小数组的数导入大数组。
`假设A是一个数组，p<=q<r，pqr分别是数组下标。`
`假设子数组A[p,q],A[q+1,r]都已经排好序`
`n=r-p+1是待合并的元素总数`
`n1=q-p+1`
`n2=r-q`
`let L[1,n1+1] and R[1,n2+1] be a new arrays`
`for i=1 to n1`
` L[i]=A[p+i-1]`
`for j=1 to n2`
`L[n1+1]=*(书上用的无穷我懒得找)`
`R[n2+1]=*`
`i=1;j=1`
`for k=p to r`
`if L[i]<=R[j]`
`A[k]=L[i]`
`i=i+1`
`else A[k]=R[j]`
`j=j+1`
【注意】这是伪代码。for i to/for i in range是一样的，是一个循环，表示由i=1开始进入循环，到i=n1时结束循环【归并排序】菜鸟教程中的c迭代实现 https://www.runoob.com/w3cnote/merge-sort.html
`int min(int x, int y) {`
` return x < y ? x : y;`
`}`
`void merge_sort(int arr[], int len) {`
` int *a = arr;`
` int *b = (int *) malloc(len * sizeof(int));`
` int seg, start;`
` for (seg = 1; seg < len; seg += seg) {`
` for (start = 0; start < len; start += seg * 2) {`
` int low = start, mid = min(start + seg, len), high = min(start + seg * 2, len);`
` int k = low;`
` int start1 = low, end1 = mid;`
` int start2 = mid, end2 = high;`
` while (start1 < end1 && start2 < end2)`
` b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];`
` while (start1 < end1)`
` b[k++] = a[start1++];`
` while (start2 < end2)`
` b[k++] = a[start2++];`
` }`
` int *temp = a;`
` a = b;`
` b = temp;`
` }`
` if (a != arr) {`
` int i;`
` for (i = 0; i < len; i++)`
` b[i] = a[i];`
` b = a;`
` }`
` free(b);`
`}`【归并排序】菜鸟教程中的c递归排序（递归出门上走）https://www.runoob.com/w3cnote/merge-sort.html
`void merge_sort_recursive(int arr[], int reg[], int start, int end) {`
` if (start >= end)`
` return;`
` int len = end - start, mid = (len >> 1) + start;`
` int start1 = start, end1 = mid;`
` int start2 = mid + 1, end2 = end;`
` merge_sort_recursive(arr, reg, start1, end1);`
` merge_sort_recursive(arr, reg, start2, end2);`
` int k = start;`
` while (start1 <= end1 && start2 <= end2)`
` reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];`
` while (start1 <= end1)`
` reg[k++] = arr[start1++];`
` while (start2 <= end2)`
` reg[k++] = arr[start2++];`
` for (k = start; k <= end; k++)`
` arr[k] = reg[k];`
`}`
`void merge_sort(int arr[], const int len) {`
` int reg[len];`
` merge_sort_recursive(arr, reg, 0, len - 1);`
`}`【归并排序】也许菜鸟教程的实现太过麻烦.......那来继续看书
前面那个只是主要思想，还有个问题就是要分到什么时候为止，循环怎么弄
好办，把上面那个当成子程序。
A[p，r]中，若p>=r，那么数组最多有一个元素，所以已经排好序。否则继续分下标，A【p，q】和A【q+1，r】，前者包含2/n向下取整，后者包含2/n向上取整个元素
if p<r
q=向下取整(p+r)/2
叠自己（A , p , q）
叠自己（A ，q+1，r）
叠上面（A，p，q，r）
叠自己是指这一整个if语句
更不能理解了对吧，还是看菜鸟吧，啧 或者再来一个？https://blog.csdn.net/ds19980228/article/details/82863531 度受版：
` void Merge(int sourceArr[],int tempArr[], int startIndex, int midIndex, int endIndex)`
` {`
` int i = startIndex, j=midIndex+1, k = startIndex;`
` while(i!=midIndex+1 && j!=endIndex+1)`
` {`
` if(sourceArr[i] > sourceArr[j])`
` tempArr[k++] = sourceArr[j++];`
` else`
` tempArr[k++] = sourceArr[i++];`
` }`
` while(i != midIndex+1)`
` tempArr[k++] = sourceArr[i++];`
` while(j != endIndex+1)`
` tempArr[k++] = sourceArr[j++];`
` for(i=startIndex; i<=endIndex; i++)`
` sourceArr[i] = tempArr[i];`
` }`
` //内部使用递归`
` void MergeSort(int sourceArr[], int tempArr[], int startIndex, int endIndex)`
` {`
` int midIndex;`
` if(startIndex < endIndex)`
` {`
` midIndex = startIndex + (endIndex-startIndex) / 2;//避免溢出int`
` MergeSort(sourceArr, tempArr, startIndex, midIndex);`
` MergeSort(sourceArr, tempArr, midIndex+1, endIndex);`
` Merge(sourceArr, tempArr, startIndex, midIndex, endIndex);`
` }`
` }`
` int main(int argc, char * argv[])`
` {`
` int a[8] = {50, 10, 20, 30, 70, 40, 80, 60};`
` int i, b[8];`
` MergeSort(a, b, 0, 7);`
` for(i=0; i<8; i++) `
` printf("%d ", a[i]); `
` printf("\n"); `
` return 0; `
` } ` (自己还没敲.......恩流下了不学无术的泪水
JunYearPrisoner
commented
4 years ago 【桶排序】 搜了一大堆讲的乱七八糟的咱也听不懂。核心就一句话：将数组一的值作为数组二的下标，数组一中每读取到一个同样的值就将这个下标对应的数组二的值加一。 用于数据去重的桶排序：
`#include <stdio.h>`
`int main()`
`{`
` int a[32767]={0};`
` int b[10];`
` for(int i=0;i<10;i++){`
` scanf("%d",&b[i]);`
` }`
` for(int i=0;i<10;i++){`
` a[b[i]]=a[b[i]]+1;`
` //将b[i]的值作为a的下标，数组b每读到一个相同的数，`
` //a中这个下标对应的值都会+1； `
` }`
` for(int i=0;i<32767;i++){`
` if(a[i]>0){`
` printf("%d ",i);`
` }`
` }`
` return 0;`
`} `正常的：https://blog.csdn.net/weixin_42558965/article/details/105623799
【冒泡排序】 对，没错，就是很简单但是很难理解的还没sort（）方便（毕竟要自己打2333）的冒泡排序。 工作原理：不断进入循环对比相邻两个数的大小，小的放前面大的放后面（可以调整）。所以每一次循环后最后一位数一定是最大的。那么要遍历的数每次都减一，节省下时间。举个栗子： 9 4 5 3 第一次循环： 4 5 3 9 第二次循环： 4 3 5 9 第三次循环： 3 4 5 9 当然也是有图的：https://www.runoob.com/wp-content/uploads/2019/03/bubbleSort.gif 这就需要两个循环，那上面那个说外循环的次数是4-1=3次；里循环每次要跑到4-1-正在进行的第x轮外循环处。 上代码：
嗯，这就完了，就这么几句话.................所以我当初看的那么大一串又臭又长的解释到底是什么..............