c++实现排序算法、swap函数的简单实现(代码只是大概意思不一定能运行) 冒泡排序插入排序希尔排序堆排序归并排序快排表排序基数排序swap函数实现
冒泡排序 void 鲜艳的牛排_sort(int a[], int num){for (int p = num - 1; p >= 0; p--){int flag = 0;for (int i = 0; i < p; i++){if (a[i] < a[i + 1]){swap(a[i], a[i + 1]);}flag = 1;}if (flag == 0)break; //全程无交换退出}} //从后往前遍历后面的比前面的小交换,或者从前向后便利将大的放在后面 O(n^2) 交换相近元素下界(n^2)
从后往前遍历后面的比前面的小交换,或者从前向后便利将大的放在后面 O(n^2) 交换相近元素下界(n^2)
插入排序 void insert_sort(int a[], int num){for (int p = 1; p < num; p++){int temp = a[p];int location = 1;for (int i = p; i > 0 && a[i - 1] > a[p]; i--){a[i] = a[i - 1]; //向后移一个若移动a[p]已经改变location = i - 1; //记录当前遍历的元素的位置}a[location] = temp;}}//插入排序 顺序看数组中的每一个数 从第二个数开始与之前的数比较//面的数大则向后错去报从小到达的顺序最后在将数放入 最快O(n) 最慢O(n^2) 上界(n^2)//相对于冒泡排序而言不需要每次比较都交换位置 冒泡每一项都需要看但是插入排序若顺序正确那么只需比较最后一个插入排序 顺序看数组中的每一个数 从第二个数开始与之前的数比较
前面的数大则向后移 从小到大的顺序最后在将数放入 最快O(n) 最慢O(n^2) 上界(n^2)
相对于冒泡排序而言不需要每次比较都交换位置 冒泡每一项都需要看但是插入排序若顺序正确那么只需比较最后一个
一串数字中的逆序对决定了交换次数而冒泡排序与插入排序相 同
思路 冒泡排序插入排序一次只能消灭一个逆序对,一次多消灭几个逆序对 不再相邻交换跳着交换
希尔排序最外层是增量的循环内部是一个插入排序但是希尔排序最坏的情况下他的排序复杂度为增长速度真的是(n^2)
堆排序 void selection_sort(int a[], int n){//position=findmin();怎么找到最小元 堆排序//swap(a[i],a[position])}//选择排序 每次选择未排序的最小元 将为排序部分的最小元换到已排序的最后部分void PercDown(int A[], int p, int N){ /* 改编代码4.24的PercDown( MaxHeap H, int p ) *//* 将N个元素的数组中以A[p]为根的子堆调整为最大堆 */int Parent, Child;int X;X = A[p]; /* 取出根结点存放的值 */for (Parent = p; (Parent * 2 + 1) < N; Parent = Child){Child = Parent * 2 + 1;if ((Child != N - 1) && (A[Child] < A[Child + 1]))Child++; /* Child指向左右子结点的较大者 */if (X >= A[Child])break; /* 找到了合适位置 */else /* 下滤X */A[Parent] = A[Child];}A[Parent] = X;} //每个分支确保父节点最大void HeapSort(int A[], int N){ /* 堆排序 */int i;for (i = N / 2 - 1; i >= 0; i--) /*从后向前建立最大堆 */PercDown(A, i, N);for (i = N - 1; i > 0; i--){/* 删除最大堆顶 */swap(A[0], A[i]); /* 见代码7.1 */PercDown(A, 0, i); //每次将最后堆的叶子节点与第一个最大的父元素交换位置 //再将剩下的元素重新进行堆排序}} // 复杂度nlogn 归并排序 //有序子列的归并 各序列每一项按顺序比较合并O(n) 递归分而治之的应用void merge(int a[], int temp[], int l, int r, int rightend){//将a[l]-a[r-1] 和 a[r]-a[rightend]合并为一个子序列int leftend = r - 1; // 左边终点位置int position = l;//合并序列的其起始下表为lwhile (l <= leftend && r <= rightend){if (a[l] <= a[r]){temp[position++] = a[l++];}/* 将左边元素复制到TmpA */else{temp[position++] = a[r++];}/* 将右边元素复制到TmpA */}while (l <= leftend){temp[position++] = a[l++];}while (r <=rightend){temp[position++]= a[r++];}int NumElements = rightend;for(int i = 0; i < NumElements; i++, rightend -- ) a[rightend] = temp[rightend]; /* 将有序的TmpA[]复制回A[] */}void merge_sort(int a[], int temp[], int left, int right){int center;if (left < right){//将一个数列从左右拆分只有一个元素时停止拆分合并center = (left + right) / 2;merge_sort(a, temp, left, center);merge_sort(a, temp, center, right);merge(a, temp,left,center+1,right);}}void MergeSort( int A[], int N ){ /* 归并排序 */ int *TmpA; TmpA = (int *)malloc(N*sizeof(int)); if ( TmpA != NULL ) { merge_sort( A, TmpA, 0, N-1 ); free( TmpA ); } else printf( "空间不足" );} 快排主元的选择 每次取头尾中间的三个数互换位置小大中 并将中间的元素放在序列的倒数第二个 两个指针分别从头和尾前进
按照最后元素进行比较交换进而能够确认所选主元的准确位置
表排序的实现 n个数字排列会由若干个独立的环组成 见每个换对应位置放对
基数排序基数排序之前的几种排序都是根据比较大小的方法来进行排序最快nlogn
桶排序 开足够大的数组 每一个元素对应值放进数组的对应下标之中
基数排序 此为优先原则 对应n个数 每一个数按照位数从低到高进行排序
基数排序 - 次位优先