概叙

相关知识点：

• 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。

• 不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。

• 时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。

• 空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数

2.它们之间的性能比较：

当n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序``堆排序 归并排序

排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序，而外部排序是排序的数据很大，一次不能容纳全部的排序记录，而排序过程中需要访问外存

八大排序就是内部排序。

插入排序

简单插入排序

算法描述：

• 从第一个元素开始划分出一个有序的序列
• 依次取出下一个元素,在已经排序的元素序列中从后向前扫描
• 如果已排序元素大于新元素，该元素移到下一个我位置
• 重复步骤3，直到找到新元素所在位置
• 重复2，5步骤
  

c语言实现：

 #直接插入排序#include<stdio.h>
#include<string.h>
void InsertionSort(int* arr,int len)
{int i ,j;for (i = 1;i <= len;i++){j = i;while (j--){if (arr[j - 1] > arr[j]){int temp = arr[j - 1];arr[j - 1] = arr[j];arr[j] = temp;}else{break;//小于退出while循环提高效率}}}
}
int main()
{int arr[] = {8,3,9,5,6,7,1,4,0,2};int i = 0;int len = sizeof(arr) / sizeof(arr[0]);InsertionSort(arr,len);for (i = 0;i < (sizeof(arr) / sizeof(arr[0]));i++){printf("%d ", arr[i]);}system("pause");return 0;
}

希尔排序

算法描述：

又称缩小增量排序

• 选择一个增量序列
• 每趟排序，根据对应的增量t，进行两两数据比较，将小的放在前，大的放在后
• 重复第二步，直到增量已用尽

简单选择排序的基本思想：比较+交换

c语言实现：

#include<stdio.h>
#include<stdlib.h>
void swap(int* L, int* R)
{int temp = *L;*L = *R;*R = temp;
}
void ShellSort(int* arr, int len)
{for (int gap = (len / 2); gap > 0;gap /= 2)//设置gap起始间距为长度的一半{//以gap为间距组从一个组，每次对这个组进行直接插入排序for (int i = gap; i < len;i++)//以gap位置为起始，找到每一个元素以gap间隔为组向前进行直接插入排序{int j = i;while ((arr[j]< arr[j - gap]) && j - gap >= 0){swap(&arr[j],&arr[j -gap]);j -= gap;//找到之前所有的成员比较并排序}	}}
}int main()
{int arr[] = { 8,3,9,5,6,7,1,4,0,2 };int i = 0;int len = sizeof(arr) / sizeof(arr[0]);ShellSort(arr, len);for (i = 0;i < len;i++){printf("%d ", arr[i]);}system("pause");return 0;
}

交换排序

冒泡排序

算法描述：

• 第一轮从头到尾对n个元素进行两两比较，进行调换位置
• 需要对余下的n-1个数据进行从头到尾两两比较直到数据有序为止

c语言实现：

#include<stdio.h>
#include<string.h>
void bubbleSort(int* arr,int len)
{int i, j;for (i = 0;i < len - 1;i++){for (j = 0;j < len - 1 - i;j++){if (arr[j] > arr[j + 1]){int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}
}
int main()
{int i;int arr[] = {6,3,8,7,5,4,1,2,0};int len = sizeof(arr) / sizeof(arr[0]);bubbleSort(arr,len);for (i = 0;i < (sizeof(arr) / sizeof(arr[0]));i++){printf("%d ", arr[i]);}system("pause");return 0;
}

快速排序

算法描述：

实例排序：

一趟排序结果：{49 38 65 97 76 13 27 49’}

二趟排序结果：{27 38 13} 49 {76 97 65 49’}

三趟排序结果：{13} 27 {38} 49 {76 97 65 49’}

四趟排序结果：13 27 38 49 {49’ 65} 76 {97}

• 定义low和high指向头尾两个关键数据

• 将low所指数据与其后面数据进行比较，如果比其小就把它放在该数据的前面

• 将high所指数据与其后面数据进行比较，如果比其大就把它放在该数据的后面

• 当low和high指针所指数据重叠时，将数据分为两组，重新设置头尾数据为low和high，重复上述操作，直至数据有序

c语言实现：

#include<stdio.h>
#include<string.h>
#include<assert.h>void QuickSort(int* arr,int left, int right)
{int i = left; int j = right;int temp = arr[i];if (i >= j)return;while (i != j){while (arr[j] >= temp && i < j){j--;}if (i < j){arr[i] = arr[j];}while (arr[i] <= temp && i < j){i++;}if ( i < j){arr[j] = arr[i];}}arr[i] = temp;QuickSort(arr,left,i - 1);QuickSort(arr, i + 1, right);
}int main()
{int arr[] = {8,3,9,5,6,7,1,4,0,2};int i = 0;int len = sizeof(arr) / sizeof(arr[0]);QuickSort(arr,0,len - 1);for (i = 0;i < len ;i++){printf("%d ", arr[i]);}system("pause");return 0;
}

选择排序

简单选择排序

算法描述：

• 在第一个位置开始从数组找到最小的数据

• 往下一个位置开始找到数组中最小的数据

• 重复第二步，直到数组有序为止

c语言实现：

#include<stdio.h>
#include<string.h>
void SelectionSort(int* arr, int len)
{int min;//保存当前最小数字下标for (int i = 0;i < len - 1;i++){min = i;for (int j = i + 1;j < len; j++){if (arr[min] > arr[j]){min = j;}}int temp = arr[min];arr[min] = arr[i];arr[i] = temp;}}
int main()
{int arr[] = {8,3,9,5,6,7,1,4,0,2};int i = 0;int len = sizeof(arr) / sizeof(arr[0]);SelectionSort(arr,len);for (i = 0;i < len ;i++){printf("%d ", arr[i]);}system("pause");return 0;
}

堆排序

算法描述：

堆就是用数组实现的二叉树，所以没有父指针或字指针

堆分为两种：最大堆 和最小堆

两者区别：

节点的值比每一个子节点的值都要大

节点的值比每一个子节点的值都要小

鉴于最大堆和最小堆是对称关系，理解其中一种即可。所以接下来我们为你们说明一下最大堆的排序

最大堆进行升序排序的思想：
1.
初始化堆：将数列a[1…n]构成最大堆

交换数据：将a[1]和a[n] 交换，使a[n]是a[1…n]中的最大值；然后将a[1…n-1]重新调整为最大堆。 接着，将a[1]和a[n-1]交换，使a[n-1]是a[1…n-1]中的最大值；然后将a[1…n-2]重新调整为最大值。 依次类推，直到整个数列都是有序的。

c语言实现：

#include<stdio.h>
#include<string.h>
#include<assert.h>
void AdjustHead(int *arr, int parent, int len)
{//大堆assert(arr);int child = parent * 2 + 1;while (child < len){if (arr[child] < arr[child + 1] && child + 1 < len){child += 1;//左子树小于右子树交且合法时交换}if (arr[child] > arr[parent]){//将大值交给父亲节点int temp = arr[child];arr[child] = arr[parent];arr[parent] = temp;//复位，再次判断，防止左右孩子都大于双亲parent = child;child = parent * 2 + 1;}elsereturn;//不满足退出}
}
void HeapSort(int* arr, int len)
{//建堆int root = (len - 2) >> 1;//找到最后一个非叶子节点for (root;root >= 0;--root){AdjustHead(arr, root, len);}//排序int end = len - 1;while (end){int temp = arr[0];arr[0] = arr[end];arr[end] = temp;//循环排序每一个元素AdjustHead(arr,0,end);end--;}
}
int main()
{int arr[] = {8,3,9,5,6,7,1,4,0,2};int i = 0;int len = sizeof(arr) / sizeof(arr[0]);HeapSort(arr,len);for (i = 0;i < len ;i++){printf("%d ", arr[i]);}system("pause");return 0;
}

归并排序

归并排序

算法描述：

• 将长度为n的输入序列分为长度为n/2的子序列
• 对两个子序列分别采用归并排序
• 将两个排序号的子序列合并成一个最终的排序序列

c语言实现：

#include<stdio.h>
#include<string.h>
#include<assert.h>
//合并
void Merge(int* arr, int low, int mid, int high)
{int i = low;//第一组下标int j = mid + 1;//第二组下标int k = 0;int arr2[100] = {0};//临时排序存放序列
//循环判断arr[i]和arr[j]的值，谁小谁放在arr2中while (i <= mid && j <= high){if (arr[i] <= arr[j]){arr2[k] = arr[i];i++;k++;}else{arr2[k] = arr[j];j++;k++;}}//当至少一组放完后，剩下的全部按顺序放入arr2（已经有序的数组）//最后一组元素可能不过正常数量while (i <= mid){arr2[k] = arr[i];i++;k++;}while (j <= high){arr2[k] = arr[j];j++;k++;}//将arr2中的序列复制到arr中for (k = 0, i = low;i <= high;i++, k++){arr[i] = arr2[k];}}void MergeSort(int *arr, int len)
{
//间隔增加（gap就是一组几个元素）for( int gap = 1;gap < len;gap = (gap * 2) ){int i = 0;//从间隔gap开始排序for (i = 0;i + 2*gap - 1 < len;i = i + 2*gap){Merge(arr, i , i + gap - 1 , i + 2*gap - 1 );}//当gap大于len的一半时，排序for无法排序的两个子组if (i + gap - 1 < len) {Merge(arr, i, i + gap - 1, len - 1);}}
}int main()
{int arr[] = {8,3,9,5,6,7,1,4,0,2};int i = 0;int len = sizeof(arr) / sizeof(arr[0]);MergeSort(arr,len );for (i = 0;i < len;i++){printf("%d ", arr[i]);}system("pause");return 0;
}