700字范文 > 王道八大排序：直接插入排序折半插入排序希尔排序冒泡排序快速排序归并排序

王道八大排序：直接插入排序折半插入排序希尔排序冒泡排序快速排序归并排序

时间：2020-06-21 07:53:39

文章目录

1、插入排序1.1直接插入排序1.2折半插入排序1.3希尔排序 2、交换排序2.1冒泡排序2.2快速排序 3、选择排序3.1简单选择排序3.2堆排序 4、归并排序5、基数排序

1、插入排序

1.1直接插入排序

直接插入排序：每次将当前元素按照其大小插入到前面已有序的子序列中。

//arr[0~n-1]存数据；void InsertSort(int arr[], int n){int i, j, temp;//遍历数组for (i = 1; i < n; i++){//当前元素的前驱大于当前元素if (arr[i - 1] > arr[i]) {temp = arr[i]; //保存arr[i]//将前面有序序列中的所有大于arr[i]的值全部后移一位for (j = i - 1; j >= 0 && arr[j] > temp; j--){arr[j + 1] = arr[j];}arr[j + 1] = temp; //将原arr[i]赋值给arr[j + 1]}//if}//for}

1.2折半插入排序

折半插入排序：与折半查找类似，逐一遍历数组元素，在数组前面有序的序列中找到该元素的位置

void InsertSort(int arr[], int n) {int i, low, high, mid;//用arr[1~n]存数，arr[0]保存当前元素，将arr[1]视为有序；for (i = 2; i<=n; i++) {arr[0] = arr[i]; //初始化low和high指针分别为第一个元素和第i - 1个元素low = 1;high = i - 1;//循环直到low > high，查找当前元素在当前序列中的位置while (low <= high) {mid = (high + low) / 2; //更新mid//mid指向的元素小于arr[0]，去左半边继续排序if (arr[0] < arr[mid])high = mid - 1;//mid指向的元素大于等于arr[0]，去右半边，这是该算法稳定的原因else low = mid + 1;}//从arr[high+1]或arr[low]元素统一后移for (int j = i - 1; j >= high+1; j--) {arr[j+1] = arr[j ];}//在arr[high+1]或arr[low]处插入元素arr[high+1] = arr[0];}//for}

1.3希尔排序

希尔排序：把相隔某个增量的元素组成一个子表，对各个子表进行直接插入排序，当整个表中基本有序的时候，再对整个表进行一次直接插入排序。

void ShellSort(int arr[], int n) {int d;//初始化d为n/2，每一轮d为上一轮的1/2for (d = n / 2; d >= 1; d /= 2) {//从每个分组的第二个元素开始，遍历剩余元素，进行直接插入排序for (int i = d+1; i <= n; i++) {if (arr[i] < arr[i - d]) {//将arr[i]直接插入有序增量子表（组间元素对比）arr[0] = arr[i]; //暂存arr[0]int j;for (j = i - d; j > 0 && arr[j] > arr[0]; j -= d) {arr[j + d] = arr[j]; //记录后移}arr[j + d] = arr[0]; //插入}//if}//for}//for}

2、交换排序

2.1冒泡排序

冒泡排序：从后往前两两比较相邻元素的值，若为逆序，则交换。

//交换void swap(int& a, int& b) {int temp = a;a = b;b = temp;}//冒泡排序void BubbleSort(int arr[], int n) {for (int i = 0; i < n - 1; i++) {bool flag = false;//标记此轮循环中是否发生交换//每次从数组中最后1个元素向前遍历，直到第i个元素for (int j = n - 1; j > i; j--) {//将相邻两个元素为逆序，则交换，并更改flag。if (arr[j - 1] > arr[j]) {swap(arr[j - 1], arr[j]);flag = true;}}//for//此次循环元素都是正序，则结束函数if (flag==false) return;}//for}

2.2快速排序

快速排序：

1、取当前表中的第1个元素为基准元素，找到它在表中的位置，即左边元素都小于它，右边元素都大于等于它，这样就确定了基准元素的最终位置。

2、以它为分割，递归的对两个子表进行上述操作，直到每个表都只有1个或0个元素为止。

void swap(int& a, int& b) {int temp = a;a = b;b = temp;}void quicksort(int arr[], int L, int R) {if (L >= R) return; //当前区间中元素为1或0，则退出int pivot, i = L, j = R; //i,j是两个数组下标移动//此处可做优化，将任意一个元素与arr[L]交换pivot = arr[L];while (i < j) {while (i<j && arr[j]>pivot) j--;while (i < j && arr[i] <= pivot)i++;if (i < j) //避免++--之后不满足i<j；swap(arr[i], arr[j]);}swap(arr[L], arr[i]);//此时A[L~i-1] <= A[i]<=A[i+1~R];quicksort(arr, L, i - 1); //递归左区间quicksort(arr, i + 1, R);//递归右区间}

3、选择排序

3.1简单选择排序

简单选择排序：遍历数组，每次找到一个最小的元素插入到待排序表的表头位置。

//交换元素void swap(int& a, int& b) {int temp = a;a = b;b = temp;}//简单选择排序void SelectSort(int arr[], int n) {//遍历数组 arr[0~n-2] 最后一个元素arr[n-1]不用遍历；for (int i = 0; i < n-1; i++) {int min = i;//标记未排序数列中最小值元素的下标，初始为第 i 个元素;for (int j = i + 1; j< n; j++) {//从i + 1开始遍历数组if (arr[j] < arr[min]) min = j;}//for完之后min指向未排序数列中最小值元素的下标if(min!=i) swap(arr[i], arr[min]); //交换第 i 个元素和最小值元素}}

3.2堆排序

堆排序：

1、首先建成大根堆，即堆顶元素大于左右子树的值，左右子树也满足该特性。

2、输出堆顶元素，将堆底元素送入堆顶，此时堆特性被破坏，将堆顶元素向下调整直到满足堆特性，再输出堆顶元素。

3、如此重复，直到堆中只剩一个元素为止。

//调整以k为子树的大根堆（arr[0]中自始至终只存过arr[k]）void HeadAdjust(int arr[],int k,int len) {arr[0] = arr[k];//arr[0]保存第k个元素for (int i = 2 * k; i <= len; i *= 2) {if (i < len&& arr[i] < arr[i + 1]) i++; //判断左右孩子谁更大,i指向更大的孩子；if(arr[0]>=arr[i]) break; //根节点arr[0]与大孩子的值比较，大于，则筛选结束。else {arr[k] = arr[i]; //小于，则将大孩子arr[i]调整到双亲节点上。k = i; //调整k值，以便继续向下筛选。}}//forarr[k] = arr[0]; //被筛选节点的值放入最终位置}void BuildMaxHeap(int arr[], int len) {//从分支节点开始从后往前，向上遍历调整；for (int i = len / 2; i > 0; i--) {HeadAdjust(arr,i,len); //调整以i为子树的大根堆}}//大根堆排序void HeapSort(int arr[], int len) {BuildMaxHeap(arr, len);//从后往前遍历数组for (int i = len; i > 1; i--) {swap(arr[i], arr[1]); //交换堆顶元素和堆底元素HeadAdjust(arr,1, i-1);//调整大根堆}}

4、归并排序

归并排序：将两个或多个有序表合并成一个有序表。

//Merge()函数：将前后两个有序表归并成一个有序表int *B= (int*)malloc(sizeof(int) * (maxsize+1)); //辅助数组B[]void Merge(int A[], int L, int mid, int R) {for (int k = L; k <= R; k++)B[k] = A[k]; //将A数组元素复制到B中int i, j, k;//遍历数组for (i = L, j =mid+1, k = i; i<= mid && j<= R; k++) {if (B[i] <= B[j]) A[k] = B[i++]; //比较B中的左右子表中的元素大小，两个子表若元素相同，则优先选择左子表else A[k] =B[j++]; //将较小值复制到A中}//将剩余元素插入到表中while (i <= mid) A[k++] = B[i++];//若一个表未检测完，复制while (j <= R) A[k++] = B[j++]; //若二个表未检测完，复制}void MergeSort(int A[], int L, int R) {if (L < R) {int mid =(L+ R) / 2;//从中间划分两个子序列MergeSort(A, L, mid);//对左子表进行递归排序MergeSort(A, mid + 1, R); //对右子表进行递归排序Merge(A, L,mid, R); //归并}//if}