冒选快希桶归排序总结

1.插入排序

? 插入排序是一种稳定的且快速的排序，比冒泡排序快就是了。它的思想就是一句话：

❗️❗️每一次将一个待排序的数据插入到前面已经排好序的有序序列中，直到插完所有元素为止。

给一个小小的示意图：

下面给代码

#include 
    #include 
    int a[10] = { 
    3,1,7,9,4,0,-4,2,8,13 }; void Insert_sort(int *a) //从小到大 { 
    int i, j; for (i = 1; i < 10; i++) //如果有10个元素，就要插入9次,第一个元素默认为有序数组元素， { 
    int temp = a[i]; for (j = i - 1; a[j] > temp && j >= 0; j--) //这里的a[j]>temp意思是当前有序数组元素大于待排序元素，然后继续向前遍历直到有序数组元素小于待排序元素，那么将待排序元素插入 { 
    a[j + 1] = a[j];//将元素后移，因为待排序元素要插入 } //最后将待排序元素插入 a[j+1] = temp; } } void print(int* a) { 
    for(int i = 0; i < 10; i++) printf("%d ", a[i]); printf("\n"); } int main() { 
    Insert_sort(a); print(a); return 0; } 

插入排序的代码的一个关键就是在遍历有序数组的时候每次都将数组元素往后移动一个，这样在找到插入位置的时候就可以直接将元素插入，而待排序元素一开始就用temp保存。这样有序数组往后移动的时候虽然覆盖了待排序元素，也没有关系，因为待排序元素用temp保存了。

2.希尔排序

希尔排序还有点没弄明白原理，暂时只把它背下来。下面是代码

#include 
    #include 
    #include 
    #include 
    int a[10] = { 
    3,1,7,9,4,0,-4,2,8,13 }; void Insert_sort(int *a) //从小到大 { 
    int i, j; for (i = 1; i < 10; i++) //如果有10个元素，就要插入9次,第一个元素默认为有序数组元素， { 
    int temp = a[i]; for (j = i - 1; a[j] > temp && j >= 0; j--) //这里的a[j]>temp意思是当前有序数组元素大于待排序元素，然后继续向前遍历直到有序数组元素小于待排序元素，那么将待排序元素插入 { 
    a[j + 1] = a[j];//将元素后移，因为待排序元素要插入 } //最后将待排序元素插入 a[j+1] = temp; } } void Swap(int *a,int i,int j) //交换元素 { 
    int temp = a[i]; a[i] = a[j]; a[j] = temp; } void shell_sort(int* arr, int len) //希尔排序 { 
    for (int gap = len / 2; gap > 0; gap = gap / 2) //gap是增量 { 
    for (int i = gap; i < len; i++) { 
    int j = i; while (j - gap >= 0 && arr[j] < arr[j - gap]) { 
    Swap(arr, j, j - gap); //交换值 j = j - gap; } } } } void print(int* a) //输出数组 { 
    for(int i = 0; i < 10; i++) printf("%d ", a[i]); printf("\n"); } int main() { 
    //Insert_sort(a); shell_sort(a,10); print(a); return 0; } 

3.冒泡排序

#include 
    #include 
    #include 
    #include 
    int a[10] = { 
    3,1,7,9,4,0,-4,2,8,13 }; void Insert_sort(int *a) //从小到大 { 
    int i, j; for (i = 1; i < 10; i++) //如果有10个元素，就要插入9次,第一个元素默认为有序数组元素， { 
    int temp = a[i]; for (j = i - 1; a[j] > temp && j >= 0; j--) //这里的a[j]>temp意思是当前有序数组元素大于待排序元素，然后继续向前遍历直到有序数组元素小于待排序元素，那么将待排序元素插入 { 
    a[j + 1] = a[j];//将元素后移，因为待排序元素要插入 } //最后将待排序元素插入 a[j+1] = temp; } } void Swap(int *a,int i,int j) //交换元素 { 
    int temp = a[i]; a[i] = a[j]; a[j] = temp; } void shell_sort(int* arr, int len) { 
    for (int gap = len / 2; gap > 0; gap = gap / 2) { 
    for (int i = gap; i < len; i++) { 
    int j = i; while (j - gap >= 0 && arr[j] < arr[j - gap]) { 
    Swap(arr, j, j - gap); j = j - gap; } } } } void maopao_sort(int* a) //冒泡排序 { 
    for(int i=0;i<10-1;i++) //10个元素，只需要冒泡9次就欧克 for (int j = 0; j < 10 - 1 - i; j++) //每次排完一次，那么最后面的元素就不需要动了，所以要减i。i代表排了几个了 { 
    if (a[j] > a[j + 1])//小的放前面，大的放后面，所以一旦有前面的大于后面的，就和后面的交换位置 { 
    int temp = a[j]; a[j] = a[j + 1]; a[j + 1] = temp; } } } void print(int* a) { 
    for(int i = 0; i < 10; i++) printf("%d ", a[i]); printf("\n"); } int main() { 
    //Insert_sort(a); //shell_sort(a,10); maopao_sort(a); print(a); return 0; } 

4.选择排序

知道冒泡排序，那么就知道选择排序了.选择排序的思想是：每次遍历未排序的部分，找出当前最大（最小）的元素放在未排序数组的最末端。

#include 
    #include 
    #include 
    #include 
    int a[10] = { 
    3,1,7,9,4,0,-4,2,8,13 }; void Insert_sort(int *a) //从小到大 { 
    int i, j; for (i = 1; i < 10; i++) //如果有10个元素，就要插入9次,第一个元素默认为有序数组元素， { 
    int temp = a[i]; for (j = i - 1; a[j] > temp && j >= 0; j--) //这里的a[j]>temp意思是当前有序数组元素大于待排序元素，然后继续向前遍历直到有序数组元素小于待排序元素，那么将待排序元素插入 { 
    a[j + 1] = a[j];//将元素后移，因为待排序元素要插入 } //最后将待排序元素插入 a[j+1] = temp; } } void Swap(int *a,int i,int j) //交换元素 { 
    int temp = a[i]; a[i] = a[j]; a[j] = temp; } void shell_sort(int* arr, int len) //希尔排序 { 
    for (int gap = len / 2; gap > 0; gap = gap / 2) { 
    for (int i = gap; i < len; i++) { 
    int j = i; while (j - gap >= 0 && arr[j] < arr[j - gap]) { 
    Swap(arr, j, j - gap); j = j - gap; } } } } void maopao_sort(int* a) //冒泡排序 { 
    for(int i=0;i<10-1;i++) //10个元素，只需要冒泡9次就欧克 for (int j = 0; j < 10 - 1 - i; j++) //每次排完一次，那么最后面的元素就不需要动了，所以要减i。i代表排了几个了 { 
    if (a[j] > a[j + 1])//小的放前面，大的放后面，所以一旦有前面的大于后面的，就和后面的交换位置 { 
    int temp = a[j]; a[j] = a[j + 1]; a[j + 1] = temp; } } } void choice_sort(int* a) //选择排序,每次找到一个最大的放在末尾 { 
    for(int i = 9; i>0; i--) { 
    int k = i; for (int j = i-1; j>=0;j--) { 
    if (a[k]<a[j]) //每次找到一个a[k]大的，就把这个元素标记下来,这样到最后k标记的就是最大的元素 { 
    k = j; } } //然后把标记的最大的元素和待排序元素交换位置，这个时候就把一个元素排序完了且放在数组最后面 int temp = a[i]; a[i] = a[k]; a[k] = temp; } } void print(int* a) { 
    for(int i = 0; i < 10; i++) printf("%d ", a[i]); printf("\n"); } int main() { 
    //Insert_sort(a); //shell_sort(a,10); //maopao_sort(a); choice_sort(a); print(a); return 0; } 

5.快速排序

快速排序是内排序中平均性能较好的排序，思想是每趟排序时选取一个数据（通常用数组的第一个数）作为关键数据（基准元素)，然后将所有比它小的数都放到它的左边，所有比它大的数都放到它的右边.。实际上就是一个递归过程，每趟排序完都可以保证把当前排序的元素达到一个这种状态：这个元素左边的所有元素都比它小，这个元素右边的所有元素都比他大…可想而知，每一次排序完当前元素都会有这个性质：“左边比我小，右边比我大”。那么最后一次排序完，所有的元素都满足了：“左边比我小，右边比我大”的时候，就彻底排序完了。
可以这样理解，每次排序都会使一个元素满足”我左边比我小（等于），我右边比我大（等于）“，那么当n次排序后，n个元素都满足了”我左边比我小（等于），我右边比我大（等于）“，那就是排序完了，因为一串数字，其中每个数字都满足大于等于它前面一个数组且小于等于它后面一个数字，那么这个数字串就一定是一个严格的递增数列
小声说一句：

快速排序是最快的（除了难搞的桶排序），无脑选择好吧。(下面是模板)

#include 
    #include 
    using namespace std; int arr[10]; void fast_sort(int* arr, int left, int right) { 
    int L = left; int R = right; int temp = 0; if (L < R) //每次排完序都会使子区间缩减，当子区间不成立"左小于右"的时候就是递归终止的时候 { 
    temp = arr[L]; //将基准元素先copy一下 while (L != R) { 
    while (L < R && arr[R] >= temp) //当找到一个元素小于基准元素的时候交换位置(小的放左边） R--; arr[L] = arr[R];//小的放左边left while (L < R && arr[L] <= temp) //当找到一个元素大于基准元素交换 L++; arr[R] = arr[L]; //大的放右边right } arr[L] = temp;//最后别忘了把基准元素归位//arr[R]=temp也可以，反正最后跳出循环的条件就是L==R fast_sort(arr, left, L - 1); //确定好一个元素位置（排序一趟），然后这个元素的左边所有元素再去排序 排完序的元素的位置使L，也是R fast_sort(arr, R + 1, right);//确定好一个元素位置（排序一趟），然后这个元素的右边所有元素再去排序 } } int main() { 
    for (int i = 0; i < 10; i++) cin >> arr[i]; fast_sort(arr,0,9); for (int i = 0; i < 10; i++) cout << arr[i] << " "; return 0; } 

6.桶排序

最简单的桶排序的就是将要排序的值当作数组的下标，然后从头到尾遍历数组。但是如果待排序的数组非常大，比如说1000万，那么开辟下标为1000万的数组显然不合理，那么就要有更加合理的桶函数，使之可以映射到桶里面。?❤️???

#include 
    #include 
    typedef struct node { 
    int key; struct node* next; }KeyNode; //存放节点 void bucket_sort(int keys[],int size,int bucket_size); //插入元素 int main() { 
    int a[]={ 
   11,11,9,21,14,55,77,99,53,25}; //初始化 int size=sizeof(a)/sizeof(a[0]); bucket_sort(a,size,10); return 0; } void bucket_sort(int keys[],int size,int bucket_size) { 
    KeyNode **bucket_table=(KeyNode**)malloc(bucket_size*sizeof(KeyNode*)); //定义一个2维指针，第二维用来存放当前桶的元素个数 for(int i=0;i<bucket_size;i++) { 
    //初始化桶 bucket_table[i]=(KeyNode*)malloc(sizeof(KeyNode)); bucket_table[i]->key=0; bucket_table[i]->next=NULL; } for(int i=0;i<size;i++) { 
    KeyNode* node=(KeyNode*)malloc(sizeof(KeyNode)); node->key=keys[i]; node->next=NULL; int index=keys[i]/10;//给数据分类的方法（关系到排序速度，很重要） KeyNode *p=bucket_table[index]; if(p->key==0) { 
    p->next=node; p->key++; } else{ 
    while(p->next!=NULL&&p->next->key<=node->key) //这一步保证每次装入元素都更新了当前桶的有序状态,即从小到大排序 { 
   //=的时候后来的元素会排在后面 p=p->next; } node->next=p->next; //将节点p插入node和node->next之间。 p->next=node; (bucket_table[index]->key)++; //每插入一个，桶的容量+1 } } KeyNode* k=NULL; for(int i=0;i<bucket_size;i++) //顺序输出 { 
    for(k=bucket_table[i]->next;k!=NULL;k=k->next) { 
    printf("%d ",k->key); } } } 

7.归并排序

归并排序：分治思想，先把大问题分成小问题，先解决小问题，再解决大问题。先“分”再“治”。（看到的一张非常厉害的网友的图，偷图？ 读书人的事叫借鉴⭐️⭐️

那么很明显，最直接的思路就是递归。
那么有两个问题：1.怎么递归，2.递归的时候（也就是解决子问题应该具体做什么？）

void merge_sort(int left,int right) //递归二分，一直分，分成子问题，然后 { 
    if (right > left) { 
    int mid = (right + left) / 2; merge_sort(left, mid); merge_sort(mid + 1, right); } } 

第二步，归并；

void merge(int left, int mid, int right)//归并 { 
    int L = left; //左半部分的起点 int R = mid + 1; //右半部分的起点 int k = 0; //辅助数组temp的下标 while (L <= mid && R <= right) //2路归并 { 
    if (a[L] <= a[R]) //从小到大排序 { 
    temp[k] = a[L]; L += 1; k += 1; } else //a[L]>a[R] { 
    temp[k] = a[R]; R += 1; k += 1; } } //别急，别以为这就完了，2路归并，当一路全部进入temp之和，还有一路没有遍历完。然后把另一路从当前位置全部放入tmep if (L !=(mid+1)) //左半部分没有遍历完 { 
    for (int i = L; i <= mid; i++) temp[k++] = a[i]; } if (R != (right + 1)) //右半部分没有遍历完 { 
    for (int i = R; i <= right; i++) temp[k++] = a[i]; } //别急，还没完，还要把temp的数据还给a k = 0; int temp_temp = left; for (int i = temp_temp; i <= right; i++) { 
    a[i] = temp[k]; k++; } } 

第三步，递归加归并

#include 
    #include 
    int a[] = { 
    3,1,8,7,2,0,-7,56,8,4 }; int temp[10]; //辅助数组 void merge(int left, int mid, int right)//归并 { 
    int L = left; //左半部分的起点 int R = mid + 1; //右半部分的起点 int k = 0; //辅助数组temp的下标 while (L <= mid && R <= right) //2路归并 { 
    if (a[L] <= a[R]) //从小到大排序 { 
    temp[k] = a[L]; L += 1; k += 1; } else //a[L]>a[R] { 
    temp[k] = a[R]; R += 1; k += 1; } } //别急，别以为这就完了，2路归并，当一路全部进入temp之和，还有一路没有遍历完。然后把另一路从当前位置全部放入tmep if (L != (mid + 1)) //左半部分没有遍历完 { 
    for (int i = L; i <= mid; i++) temp[k++] = a[i]; } if (R != (right + 1)) //右半部分没有遍历完 { 
    for (int i = R; i <= right; i++) temp[k++] = a[i]; } //别急，还没完，还要把temp的数据还给a k = 0; int temp_temp = left; for (int i = temp_temp; i <= right; i++) { 
    a[i] = temp[k]; k++; } } void merge_sort(int left,int right) //递归解决问题 { 
    if (right > left) { 
    int mid = (right + left) / 2; merge_sort(left, mid); merge_sort(mid + 1, right); merge(left, mid, right); } } int main() { 
    merge_sort(0, 9); for (int i = 0; i < 10; i++) printf("%d ",a[i]); return 0; } 

好了，先记录到这里把，以后要用的时候再深入学习一下.