排序算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了排序算法,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含5560字,纯文字阅读大概需要8分钟。
内容图文
![排序算法](/upload/InfoBanner/zyjiaocheng/1053/9d16a34409e641a7b310f7be6db44cc0.jpg)
#define LENGTH(array) ( (sizeof(array)) / (sizeof(array[0])) ) #define swap(a,b) do{a=a+b;b=a-b;a=a-b;}while(0) //两个数相同时 会导致结果为0
一、插入排序
1、直接插入排序
1 /* * 2 ** 直接插入排序(插入到准确的位置) 不利于二分查找 直接遍历 3 ** 时间复杂度:比较和移动和平均时间复杂度为O(n^2) 适合基本有序的序列,此时复杂度接近O(n) 4 ** 空间复杂度:O(1) 5 ** 稳定性:稳定 6 * */ 7 void InsertSort(int a[], int n) 8{ 9int i, j; 10for (i = 2; i <=n; i++)//假设第一项已经排好,所以从第二项开始11 { 12if (a[i] < a[i - 1])//若此项小于 前面已经排好的最后一项(已排好的最大项)13 { 14 a[0] = a[i];//0号位置为哨兵节点15for (j = i - 1; a[0] < a[j]; j--)//从后 向前查找待插入位置16 { 17 a[j+1] = a[j];//记录后移18 } 19 a[j+1] = a[0];//复制到插入的位置 此时a[j]已经是小于a[0]的了20 } 21 } 22 }
2、利用二分查找的直接插入排序
1 /* * 2 ** 插入排序(插入到准确的位置) 利用二分查找 3 ** 比较复杂度:O(nlogn) 4 ** 移动复杂度:O(n^2) 5 ** 时间复杂度为:O(n^2) 6 ** 稳定性:稳定 7 * */ 8 void BInsertSort(int a[], int n) 9{ 10int i, j, low, high, mid; 11for (i = 2; i <= n; i++) 12 { 13 a[0] = a[i];//哨兵元素14 low = 1; high = i - 1; 15while (low <= high) 16 { 17 mid = (low + high) / 2; 18if (a[mid] > a[0]) 19 high = mid - 1; 20else21 low = mid + 1; 22 } 23for (j = i - 1; j >=high+1; j--) 24 a[j + 1] = a[j]; 25 a[high + 1] = a[0]; 26 } 27 }
3、希尔排序
1 /* * 2 ** 希尔排序 (缩小增量的排序) 3 ** 最坏时间复杂度:O(n^2) 4 ** 平均时间复杂度:O(n^1.3) 5 ** 空间复杂度:O(1) 6 ** 稳定性:不稳定 当相同关键字被划分到不同子表时 可能会造成不稳定 7 * */ 8 void ShellSort(int a[], int n) 9{ 10//a[0] 是暂存单元 不是哨兵 11//进行插入排序的步长是dk 而不是112int i, j, dk; 13for (dk = n / 2; dk >= 1; dk = dk / 2)//步长变化14 { 15for (i = dk + 1; i <= n; i++)//对已经分好组的进行插入 排序 每一组都交替进行16 { 17if (a[i] < a[i - dk])//若当前项小于本组前一项18 { 19 a[0] = a[i];//暂存在a[0]20for (j = i - dk; j > 0 && a[0] < a[j]; j-=dk)//从本组已经排好序的序列中找到合适的插入位置21 a[j + dk] = a[j];//记录后移22 a[j + dk] = a[0];//插入23 } 24 } 25 } 26 }
二、交换排序
1、冒泡排序
1 /* * 2 ** 冒泡排序(每次交换,将相邻中大的一个放在后面) 3 ** 最坏时间复杂度:O(n^2) 4 ** 平均时间复杂度:O(n^2) 5 ** 最好情况下的复杂度:O(n) 初始序列有序时 6 ** 空间复杂度:O(1) 7 ** 稳定性:稳定 8 * */ 9 // 最大的上浮 10 void BubbleSort(int a[], int n) 11{ 12for (int i = 0; i < n - 1; i++) 13 { 14int flag = 0; 15for (int j = 0; j < n - 1 - i; j++)//最大的向上浮16 { 17if (a[j] > a[j + 1])//此处若写等号 则变成不稳定的排序18 { 19 swap(a[j], a[j + 1]); 20 flag = 1; 21 } 22 } 23if (flag == 0) return;//一整趟都未交换一次 则已排序好 退出24 } 25 }
1 // 最小的下浮 2 void BubbleSort_m(int a[], int n) 3{ 4for (int i = 0; i < n - 1; i++) 5 { 6int flag = 0; 7for (int j = n-1; j >i; j--)//最小的向下浮 8 { 9if (a[j-1] > a[j])//此处若写等号 则变成不稳定的排序10 { 11 swap(a[j], a[j-1]); 12 flag = 1; 13 } 14 } 15if (flag == 0) return;//一整趟都未交换一次 则已排序好 退出16 } 17 }
2、快速排序
1 /* * 2 ** 快速排序(任取枢轴pivot,将其分为小于pivot,和大于pivot的两部分,此时pivot放在了最终的位置上) 3 ** 最坏空间复杂度O(n) 4 ** 平均空间复杂度O(logn) 5 ** 最坏时间复杂度:O(n^2) 6 ** 平均时间复杂度:O(nlogn) 7 ** 稳定性:不稳定 如若3为枢轴{3,2,2‘} 经过一趟排序后 {2‘,2,3} 8 * */ 9 int Partition(int a[], int low, int high)//根据枢轴划分两个区间10{ 11int pivot = a[low];//将枢轴的值存起来12while (low < high) 13 { 14while (low < high && a[high] >= pivot) --high;//若高位有比枢轴小的 结束循环15 a[low] = a[high];//将高位比枢轴小的值放到低位上 16while (low < high && a[low] <= pivot) ++low;//若低位有比枢轴大的值 结束循环 17 a[high] = a[low];//将低位比枢轴大的值放在高位上18 } 19 a[low] = pivot;//将枢轴的值放到正确的位置上20return low;//返回枢轴的位置21} 22void QuickSort(int a[], int low, int high) 23{ 24if (low < high) 25 { 26int pivotloc = Partition(a, low, high); 27 QuickSort(a, low, pivotloc - 1);//依次对两个子表进行递归排序28 QuickSort(a, pivotloc + 1, high); 29 } 30 }
三、选择排序
1、选择排序
1 /* * 2 ** 选择排序(每次选最小的) 3 ** 空间复杂度O(1) 4 ** 时间复杂度:O(n^2) 5 ** 稳定性:不稳定 如若{2,2‘,1} 经过一趟排序后 {1,2‘,2} 6 * */ 7 void SelectSort(int a[], int n) 8{ 9for (int i = 0; i < n - 1; i++) 10 { 11int min = i; 12for (int j = i + 1; j < n; j++) 13 { 14if (a[j] < a[min]) 15 min = j; 16 } 17if(min!=i) 18 swap(a[i], a[min]); 19 } 20 }
2、堆排序
1 /* * 2 ** 堆排序(每次选最小的) 3 ** 空间复杂度O(1) 4 ** 时间复杂度:O(nlogn) 建堆时间O(n) 向下平均调整时间O(nlogn) 5 ** 稳定性:不稳定 如若{1,2,2‘} 构造初始堆时将2交换到堆顶 {2,1,2‘} 最终排序为{1,2‘,2} 6 * */ 7 8 // 将堆中小的节点调整至下方 9 void AdjustDown(int a[], int k, int len) 10{ 11 a[0] = a[k];//用a[0]暂存根节点12int i; 13for (i = 2 * k; i <= len; i *= 2) 14 { 15if (i < len && a[i] < a[i + 1])//找出子数较大的一个16 i++; 17if (a[0] >= a[i])break;//如果根节点本来就大 无须调整18else//叶子节点比较大19 { 20 a[k] = a[i];//将较大的叶子节点调整到根节点21 k = i;//以原先未调整的较大的叶子节点的位置为根再进行调整 22 } 23 }//for24 a[k] = a[0];//将最初暂存的根节点的值 放到最后一个做调整的叶子节点上去25} 26//建大根堆27void BuildMaxHeap(int a[], int len) 28{ 29for (int i = len / 2; i > 0; i--)//从i=n/2到1 反复调整堆30 AdjustDown(a, i, len); 31} 32//堆排序33void HeapSort(int a[], int len) 34{ 35 BuildMaxHeap(a, len);//建立大根堆36 show(a, 1,len, "after_build_max_heap:"); 37for (int i = len; i > 1; --i)//将最后一个记录与大根堆的根节点对换38 { 39 swap(a[1], a[i]); 40 AdjustDown(a, 1, i - 1);//对根节点向下调整,序列长度为i-1 第i项为已经排列好的最大项41 } 4243 }
四、归并排序
1 /* * 2 ** 归并排序(分治法 每次分成左右两个子序列 且左右两个子序列有序) 3 ** 空间复杂度O(n) 需要辅助数组b[] 4 ** 时间复杂度:O(nlogn) 5 ** 稳定性:稳定 6 * */ 7 void Merge(int a[], int b[], int low, int mid, int high) 8{ 9//a是原数组 b是辅助数组 low-mid;mid+1-high 各自有序 将他们合并成一个有序表存放在a中10int i, j, count;//count代表当前排序好的数据11for (int k = low; k <= high; k++)//将a中所有的数据放到b中12 b[k] = a[k]; 13for (i = low, j = mid + 1, count = low; i <= mid && j <= high; count++)//选择两个有序组中更小的一个放在a中14 { 15if (b[i] < b[j]) 16 a[count] = b[i++]; 17else18 a[count] = b[j++]; 19 } 20//如下两个循环只会执行一个21while (i <= mid) a[count++] = b[i++];//若第一个表未检测完 复制22while (j <= high) a[count++] = b[j++];//若第二个表未检测完 复制23} 24void MergeSort(int a[],int b[], int low, int high) 25{ 26if (low < high) 27 { 28int mid = (low + high) / 2;//划分子序列29 MergeSort(a,b ,low, mid);//对左侧递归30 MergeSort(a,b, mid + 1, high);//右侧递归31 Merge(a, b, low, mid, high);//排序 32//show(b, 0, high+1, "b:");33 } 34 }
原文:https://www.cnblogs.com/lancelee98/p/11663379.html
内容总结
以上是互联网集市为您收集整理的排序算法全部内容,希望文章能够帮你解决排序算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。