常用的排序算法

标签：单位   重复数   而且   数组   扑克   代码   运行时   vector   nlog   排序算法 这篇博文主要讲解一下主流的几大排序算法 选择排序 思路 选择排序应该是这么多排序算法中最简单的一种排序算法了，主要思路是找到数组中最小的元素，其次，将它和数组的第一个元素交换位置（如果第一个元素就是最小的元素就和自己交换）。再次，在剩下的元素中重复此行为。 时间复杂度：O(n^2) 特点 选择排序的运行时间和输入无关 数据移动的次数最少（N次） 数组的左边始终保持有序 不稳定 代码 void selectSort(vector& arr) { for (int i = 0;i a[j]) { t = j; } } if (t != i) { int tmp = a[i]; a[i] = a[t]; a[t] = tmp; } } } 插入排序 思路 插入排序类似我们打扑克时整理牌时的操作，我们一个一个元素的来处理，每次将要插入的元素插入到其他已有顺序的数组中（数组的右边） 时间复杂度 O(n^2) 特点 数组中每个元素距离它的最终距离都不远，一个有序的大数组接一个小数组，数组中只有几个数字的位置不正确，此时用插入排序是很快的 稳定的 数组的右边是有序的 代码 void insertSort(vector& arr) { //控制循环次数，假设第一个元素是有序的 for (int i = 1;i = 0 && t 0; gap /= 2) { //插入排序 for (i = 0;i = 0 && a[k] > tmp) { a[k + gap] = a[k]; k -= gap; } a[k+gap] = tmp; } } } } } 改进版代码 void shellsort2(int a[], int n) { int j, gap; for (gap = n / 2; gap > 0; gap /= 2) for (j = gap; j = 0 && a[k] > temp) { a[k + gap] = a[k]; k -= gap; } a[k + gap] = temp; } } 归并排序 思路 归并排序，可以先递归的将数组分割直到最小单位，然后合并成一个大数组，在这个过程中进行排序 以数组中心来划分，mid = （l + r) / 2，分成两半的数组分别从头开始进行比较，利用双指针，哪个数小就把它放进答案数组中，再将该指针移动一位，继续比较。 时间复杂度 O（nlogn） 特点 归并排序是稳定的 代码 void mergeSort(int q[],int l,int r) { if (l >= r) return; int mid = l + r >> 1; mergeSort(q,l,mid); mergeSort(q,mid+1,r); int k = 0,i = l,j = mid + 1; while (i x 来进行快排 代码 void quickSort(int q[],int l,int r) { if (l >= r) return; int key = q[l]; int i = l,j = l+1,k = r; while (i key) swap(a[i],a[k--]); else i++; } quickSort(q,l,j - 1); quickSort(q,j,r); } 冒泡排序 思路 不出意外，冒泡排序是大部分接触编程的人第一个学会的排序算法，因为它很简单。比较相邻的元素。如果第一个比第二个大，就交换他们两个，一直重复到倒数第二个元素。 时间复杂度 O（n^2) 特点 冒泡排序很简单 冒泡排序是稳定的 代码 void bubbleSort(int q[],int len) { for (int i = 0;i q[j+1]) { int tmp = q[i]; q[i] = q[j+1]; q[j+1] = tmp; } } } } 常用的排序算法标签：单位   重复数   而且   数组   扑克   代码   运行时   vector   nlog   原文地址：https://www.cnblogs.com/mgd666/p/13166972.html