关键词：
排序算法
这篇博文主要讲解一下主流的几大排序算法
选择排序
- 思路
选择排序应该是这么多排序算法中最简单的一种排序算法了，主要思路是找到数组中最小的元素，其次，将它和数组的第一个元素交换位置（如果第一个元素就是最小的元素就和自己交换）。再次，在剩下的元素中重复此行为。
-
时间复杂度：O(n^2)
-
特点
- 选择排序的运行时间和输入无关
- 数据移动的次数最少（N次）
- 数组的左边始终保持有序
- 不稳定
- 代码
void selectSort(vector<int>& arr)
for (int i = 0;i < arr.size() - 1; i++)
int t = i;
for (int j = i+1;j < arr.size(); j++)
//遍历数组，找到最小的一个
if (a[t] > a[j])
t = j;
if (t != i)
int tmp = a[i];
a[i] = a[t];
a[t] = tmp;
插入排序
- 思路
插入排序类似我们打扑克时整理牌时的操作，我们一个一个元素的来处理，每次将要插入的元素插入到其他已有顺序的数组中（数组的右边）
- 时间复杂度 O(n^2)
- 特点
- 数组中每个元素距离它的最终距离都不远，一个有序的大数组接一个小数组，数组中只有几个数字的位置不正确，此时用插入排序是很快的
- 稳定的
- 数组的右边是有序的
- 代码
void insertSort(vector<int>& arr)
//控制循环次数，假设第一个元素是有序的
for (int i = 1;i < arr.size(); i++)
//待排序的第一个元素
int t = a[i];
//代表已经排序过的元素最后一个索引数
int j = i - 1;
//从后向前逐个比较已经排序过数组，如果比它小，则把后者用前者代替，数组逐个后移一个，为找到合适的位置时便与插入t
while (j >= 0 && t < a[j])
a[j+1] = a[j];
j--;
//找到了合适的位置，赋值
a[j+1] = t;
希尔排序
- 思路
希尔排序是基于插入排序的快速的排序算法，希尔排序是将待排序的数组元素 按下标的一定增量分组 ，分成多个子序列，然后对各个子序列进行直接插入排序算法排序；然后依次缩减增量再进行排序，直到增量为1时，进行最后一次直接插入排序，排序结束。
希尔排序就是分组?插入排序，分组每次都减半
-
时间复杂度 O(nlog2n)
-
特点
- 非稳定的排序
- 希尔排序的执行时间依赖于增量序列
- 代码
void shellSort(vector<int>& arr)
int i,j,gap;
//以数组的长度的一半来分组，每次分组缩小一半
for (gap = arr.size()/2; gap > 0; gap /= 2)
//插入排序
for (i = 0;i < gap; i++)
for (j = i + gap;j < arr.size(); j+= gap)
if (a[j] < a[j - gap])
int tmp = a[j];
int k = j - gap;
while (k >= 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 < n; j++)//从数组第gap个元素开始
if (a[j] < a[j - gap])//每个元素与自己组内的数据进行直接插入排序
int temp = a[j];
int k = j - gap;
while (k >= 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 <= mid && j <= r)
if (q[i] < q[j]) tmp[k++] = q[i++];
else tmp[k++] = q[j++];
while (i <= mid) tmp[k++] = q[i++];
while (j <= r) tmp[k++] = q[j++];
for (i = l,j = 0;i <= r;i++,j++) q[i] = tmp[j ];
快速排序
- 思路
快速排序是本人最喜欢的排序算法，它将一个数组分成两个子数组，将两部分独立的排序
首先确定分界点x，个人喜欢中点，不用考虑啥越界问题，然后递归处理左右两段，接着利用左右双指针算法，左边i指针先走，只要这个数小于x，i指针就一直往后走，然后移动j指针，当j指针指向的数字大于x，就一直往前走，如果两个指针没有相遇，就交换
-
时间复杂度 O（n^2) （不一定）
-
特点
- 快排是不稳定的
- 快排一般来说很快，而且都是一个套路
- 代码
void quickSort(int q[],int l,int r)
if (l >= r) return;
int i = l-1,j = r+1,x = q[l + r >> 1];
while (i < j)
while(q[++i] < x);
while(q[--j] > x);
if (i < j)
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
quickSort(q,l,j),quickSort(q,j+1,r);
- 三路快排
思路：处理数组中有大量重复数据 ，此时可以用三路快排，< x,== x, > 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 <= k)
if (a[i] < key) swap(a[i++],a[j++]);
else if (a[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 < len-1; i++)
for (int j = 0;j < len - 1; j++)
if (q[i] > q[j+1])
int tmp = q[i];
q[i] = q[j+1];
q[j+1] = tmp;
常用算法之----选择排序(代码片段)
...有简单选择排序、树型选择排序和堆排序。（这里只介绍常用的简单选择排序）b) 简单选 查看详情
常用算法(代码片段)
知识目录一、冒泡排序二、选择排序三、插入排序四、快速排序五、堆排序六、归并排序总结一、冒泡排序1、思路：首先，列表每两个相邻的数比较大小，如果前边的比后边的大，那么这两个数就互换位置。就像是冒泡一... 查看详情
常用排序算法（一)(代码片段)
本篇主要介绍排序算法中的冒泡排序选择排序和插入排序一冒泡排序1、思路：首先，列表每两个相邻的数比较大小，如果前边的比后边的大，那么这两个数就互换位置。就像是冒泡一样2、代码关键点：趟数：n-1趟无序区3、图示... 查看详情
几种常用排序算法(代码片段)
八大常用排序算法详细分析包括复杂度：排序有可以分为以下几类：(1)、交换排序：冒泡排序、快速排序(2)、选择排序：直接选择排序、堆排序(3)、插入排序：直接插入排序、希尔排序(4)、归并排序(5)、基数排序（桶排序） ... 查看详情
常用排序算法(代码片段)
简述一些常用算法，并用代码实现它。注：动图是在网上找的。（1）冒泡排序核心思想：交换序列中相邻两个整数。 测试代码：1voidbubble_sort(void)23/*4*冒泡排序：以降序为例进行说明5*比较相邻的元素，将值最小的元素交换... 查看详情
常用算法之----选择排序插入排序和希尔排序(代码片段)
一些说明我将会写一系列关于算法的博客，因为我是程序员，并不是计算机科学家，也即我是搞工程的，并不是搞学术的，所以对于我来说，最重要的就是1.有哪些算法2.这些算法的原理3.这些算法的实现4.这些算法的效率 而... 查看详情
数组的常用算法二之排序算法(代码片段)
冒泡排序冒泡排序从小到大排列publicclassTestArraypublicstaticvoidmain(String[]args)//冒泡排序从小到大排列int[]a=newint[]54,78,4,87,75;for(inti=0;i<a.length-1;i++)for(intj=0;j<a.length-1-i;j++)if(a[j]>a[j+1])in 查看详情
解析常用排序算法(代码片段)
以下我说的排序算法都是说的从小到大排序1.插入排序 1insertSort(inta[])2intlength=a.length;3intb[]=newint[length+1];4for(inti=0;i<a.length;i++)//复制数组,将下标为0的空出来作为哨兵5b[i+1]=a[i];67for(inti=1;i<b.length;i++)//找n次，每 查看详情
常用算法之----堆排序(代码片段)
预备知识堆排序 堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。首先简单了解下堆结构。堆 堆是具有以下性质的完全二... 查看详情
集中常用排序算法代码(代码片段)
1publicclassCheckSum23/**4*计算数组中数据之后为sum的两个数字5*@paramarray6*@paramsum7*/8publicvoidfindTheSum(intarray[],intsum)910//Arrays.sort(array);1112int[]copy=newint[array.length];1314MergeOrder(array,copy,0 查看详情
常用排序算法(代码片段)
语雀入口 https://www.yuque.com/along-n3gko/ezt5z9冒泡排序比较相邻的两个元素，如果前一个比后一个大，则交换位置。比较完第一轮的时候，最后一个元素是最大的元素。这时候最后一个元素是最大的，所以最后一个元素就不... 查看详情
常用的排序算法(代码片段)
...s快速排序quicksort0s0s0.001s0.011s桶排序bucketsort0s0s0s0.002s附上常用排序算法的比较（https://github.com/hustcc/JS-Sorting-Algorithm）： 查看详情
常用排序算法(代码片段)
一、冒泡排序 冒泡排序是最简单的排序算法。假设数组一共有n个元素，元素最大下标为n-1，冒泡排序的具体做法是：第一趟在序列(A[0]~A[n-1])中从前往后进行两个相邻元素的比较，若前者大，则交换，... 查看详情
java-android-常用十大排序算法(代码片段)
排序就是将一组对象按照某种逻辑顺序重新排列的过程。比如，订单按照日期排序的——这种排序很可能使用了某种排序算法。现在计算机的广泛使用使得数据无处不在，而整理数据的第一步通常就是进行排序。学习排... 查看详情
7种常用的排序算法直观感受(代码片段)
1.快速排序介绍：快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序n个项目要Ο(nlogn)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(nlogn)... 查看详情
go语言数据结构与算法—常用排序算法(代码片段)
概述所谓的排序算法，就是通过特定的算法因式将一组或多组数据按照既定模式进行重新排序。这种新序列遵循着一定的规则，体现出一定的规律。因此，经过处理后的数据便于筛选和计算，大大提升了计算效率... 查看详情
go语言数据结构与算法—常用排序算法(代码片段)
概述所谓的排序算法，就是通过特定的算法因式将一组或多组数据按照既定模式进行重新排序。这种新序列遵循着一定的规则，体现出一定的规律。因此，经过处理后的数据便于筛选和计算，大大提升了计算效率... 查看详情
常用排序算法(js)(代码片段)
复习排序算法1.冒泡排序思路：每一轮都对相邻的两个元素进行比较，如果逆序则交换位置，直到所有元素都排好序为止基本操作：代码：ArrayList.prototype.bubbleSort=()=>constlen=this.data.lengthfor(leti=0;i&l... 查看详情