1.冒泡排序 2.选择排序
3.插入排序 4.希尔排序
5.计数排序
6.归并排序 7.快速排序
Notice:数组大小为n,除计排外数组均定义为a[],下标为1~n,排序默认均为升序,时间复杂度为平均复杂度
1.冒泡排序
时间复杂度:O(N^2)
(两两元素进行比较,较小的数向前浮动)
void Bubble_sort(int a[],int n) { for(int i = 1;i < n; i++){ for(int j = 1; j <= n-i; j++){ if(a[j] > a[j+1]) swap(a[j], a[j+1]); } } }
2.选择排序
时间复杂度:O(N^2)
(不断执行 *** 作:选出未经排序的一系列数的最小值,放到数组最前面)
void Select_sort(int a[], int n) { int minx,minn; for(int i=1;i < n;i++){ //minn存放每一趟排序中的最小数,minx存放下标 minn=a[i]; minx=i; for(int j=i+1;j<=n;j++){ if(minn > a[j]) minn = a[j],minx=j; } if(minx != i) swap(a[i],a[minx]); } }
3.插入排序
时间复杂度:O(N^2)
(拿出第一个乱序数,放到已经排好序的序列的合适位置)
void insert_sort(int a[],int n) { int i,j,temp; for(i = 2; i <= n; i++) { //取出要插入的数 temp = a[i]; for(j = i; j > 1 && a[j - 1] > temp; j--) //寻找合适的插入位置 a[j] = a[j - 1]; //插入数值 a[j] = temp; } }
4.希尔排序(对半式增量)
时间复杂度:O(N^1.5)左右
(不断的进行 *** 作:在原数组中按照一定间隔mid从头到尾取出一系列数形成几个新的序列——>对每个新的序列进行排序——>序列合并)
对半式增量:
比如一个长度为8的数组,8/2 = 4,所以第一次就按间隔为4取数,那么形成的新序列的下标就是:<1 5>,<2 6>,<3 7>,<4 8>
第二次间隔为4/2 = 2,则新取出的序列为<1 3 5 7>,<2 4 6 8>
最后一次间隔就是2/2 = 1,直接进行插入排序搞定
void Shell_sort(int a[],int n) { int j,i,temp,mid; //增量定义为mid for(mid = n/2; mid > 0; mid /= 2){ //一个插入排序的过程代码,只不过要注意间隔的存在 for(i = mid; i <= n; i++){ temp = a[i]; for(j = i; j > mid; j -= mid) { if(a[j - mid] > temp) a[j] = a[j - mid]; else break; } a[j] = temp; } } }
5.计数排序
时间复杂度:O(d(n+r))
(例如a[2] = 1,意思是2这个元素出现了1次)
(适用于数据集中,数据范围较小且比较明确的情况)
#includeusing namespace std; #define MAXN 10000 int cnt[MAXN+1],n,temp;; int main(void) { //输入 memset(cnt,0,sizeof(cnt)); cin >>n; for(int i = 1; i <= n; i++){ cin >>temp; cnt[temp]++; //计数 } //输出 for(int i = 0; i <= MAXN; i++){ if(cnt[i]){ //检测数字i有没有出现过 //出现几次输出几个i for(int j = 1; j <= cnt[i]; j++) cout < 6.归并排序(递归,分治)
时间复杂度:O(nlog2n)(2是底数)
//这里a和b数组没有声明,应该写到外面,a数组是录入数据的数组 void Merge_sort(int l, int r) { //递归到了只有一个元素,直接返回 if(l == r) return; //找到中点,然后两边分别再归并 int mid = (l + r) / 2; Merge_sort(1, mid); Merge_sort(mid + 1, r); //合并序列 int p = 1, q = mid + 1; for(int i = 1; i <= r; i++){ if(q > r || (p <= mid && a[p] <= a[q])) b[i] = a[p++]; else b[i] = a[q++]; } //还原到a数组里 for(int i = 1; i <= r; i++) a[i] = b[i]; }7.快速排序
时间复杂度:O(nlog2n)(2是底数)
(找一个基准,然后将小于这个基准的数放到索引的左边,大于基准的数放到索引右边
不断执行这个 *** 作直到有序,这里基准取的是中间数)
//a数组未定义 void Quick_sort( int L, int R) { int l = L, r = R; //定义基准点 int mid = (L + R) / 2; int x = a[mid]; while(l < r){ //找到两边的逆序点 while(a[l] < x && l < r) l++; while(a[r] > x && l < r) r--; //交换 if(l < r){ swap(a[l], a[r]); l++,r--; } } //左右两边继续快排 if(L < r) Quick_sort(L, r); if(l > R) Quick_sort(l,R); }欢迎分享,转载请注明来源:内存溢出
评论列表(0条)