8种经典排序算法

>>强大,10k+点赞的 SpringBoot 后台管理系统竟然出了详细教程!

1.直接插入排序

处理场景:把新的数据插入到已经排好的数据列中。

直接插入思想:

  • 将第一个数和第二个数排序,然后构成一个有序序列

  • 将第三个数插入进去,构成一个新的有序序列。

  • 重复第二步,直到最后一个数。


Java版:

 public void insertSort(int[] array){
int len=array.length;
int insertNum;
for(int i=1;i<len;i++){
insertNum=array[i];//要插入的数
int j=i-1;//排序好的序列元素个数
while(j>=0&&array[j]>insertNum){
array[j+1]=array[j];
j--;
}
array[j+1]=insertNum;//待插入的数放在要插入的位置。
}
}

2.希尔排序

处理场景:数据量大时,时间不稳定。

  • 将数的个数设为i,取奇数n=i/2,将下标差值为n的书分为一组,构成有序序列。

  • 再取n=n/2 ,将下标差值为n的书分为一组,构成有序序列。

  • 重复第二步,直到k=1执行简单插入排序。


Java版:

 public static void shellSort(int[] array){
int len = array.length;
while (true) {
len /= 2; //增量每次减半
for (int i = 0; i < len; i++) {
for (int j = i + len; j < array.length; j += len) {//这个循环里其实就是一个插入排序
int temp = array[j];
int k = j - len;
while (k >= 0 && array[k] > temp) {
array[k + len] = array[k];
k -= len;
}
array[k + len] = temp;
}
}
if (len == 1) {
break;
}
}
}

3.简单选择排序

处理场景:待排序中取最大最小数。

  • 遍历整个序列,将最小的数放在最前面。

  • 遍历剩下的序列,将最小的数放在最前面。

  • 重复第二步,直到只剩下一个数。


Java版:

 public static void simpleSort(int[] array){
int len=array.length;
for(int i=0; i<len; i++){
//记录当前位置
int position = i;
//找出最小的数,并用position指向最小数的位置
for(int j=i+1; j<len; j++){
if( array[position]>(array[j])) {
position=j;
}
}
//交换位置
int temp=array[i];
array[i]=array[position];
array[position]=temp;
}
}

4.堆排序

处理场景:对简单选择排序的优化。

  • 将序列构建成大顶堆。

  • 将根节点与最后一个节点交换,然后断开最后一个节点。

  • 重复第一、二步,直到所有节点断开。


Java版:

   public static int[] heapSort(int[] array) {
//这里元素的索引是从0开始的,所以最后一个非叶子结点array.length/2 - 1
for (int i = array.length / 2 - 1; i >= 0; i--) {
adjustHeap(array, i, array.length); //调整堆
}

// 上述逻辑,建堆结束
// 下面,开始排序逻辑
for (int j = array.length - 1; j > 0; j--) {
// 元素交换,作用是去掉大顶堆
// 把大顶堆的根元素,放到数组的最后;换句话说,就是每一次的堆调整之后,都会有一个元素到达自己的最终位置
swap(array, 0, j);
// 元素交换之后,毫无疑问,最后一个元素无需再考虑排序问题了。
// 接下来我们需要排序的,就是已经去掉了部分元素的堆了,这也是为什么此方法放在循环里的原因
// 而这里,实质上是自上而下,自左向右进行调整的
adjustHeap(array, 0, j);
}
return array;
}

/**
* 整个堆排序最关键的地方
*/

public static void adjustHeap(int[] array, int i, int length) {
// 先把当前元素取出来,因为当前元素可能要一直移动
int temp = array[i];
for (int k = 2 * i + 1; k < length; k = 2 * k + 1) { //2*i+1为左子树i的左子树(因为i是从0开始的),2*k+1k的左子树
// k先指向子节点中最大的节点
if (k + 1 < length && array[k] < array[k + 1]) { //如果有右子树,并且右子树大于左子树
k++;
}
//如果发现结点(左右子结点)大于根结点,则进行值的交换
if (array[k] > temp) {
swap(array, i, k);
// 如果子节点更换了,那么,以子节点为根的子树会受到影响,所以,循环对子节点所在的树继续进行判断
i = k;
} else { //不用交换,直接终止循环
break;
}
}
}

/**
* 交换元素
*/

public static void swap(int[] array, int a, int b) {
int temp = array[a];
array[a] = array[b];
array[b] = temp;
}

5.冒泡排序

场景:实现简单

  • 将序列中所有元素两两比较,将最大的放在最后面。

  • 将剩余序列中所有元素两两比较,将最大的放在最后面。

  • 重复第二步,直到只剩下一个数。


Java版:

 public static void bubbleSort(int []array) {

for(int i =1;i<array.length;i++) {
for(int j=0;j<array.length-i;j++) {
if(array[j]>array[j+1]) {
int temp = array[j];
array[j]=array[j+1];
array[j+1]=temp;
}
}
}
}

6.快速排序

场景:要求时间最快时。

  • 选择第一个数为p,小于p的数放在左边,大于p的数放在右边。

  • 递归的将p左边和右边的数都按照第一步进行,直到不能递归。


Java版:

 public static int[] quickSort(int array[],int start,int end) {
int pivot = array[start];
int i = start;
int j = end;
while (i<j) {
while ((i<j)&&(array[j]>pivot)) {
j--;
}
while ((i<j)&&(array[i]<pivot)) {
i++;
}
if ((array[i]==array[j])&&(i<j)) {
i++;
} else {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
if (i-1>start){
array=quickSort(array,start,i-1);
}
if (j+1<end){
array=quickSort(array,j+1,end);
}
return (array);
}

7.归并排序

场景:速度快,并行计算,速度稳定。

  • 选择相邻两个数组成一个有序序列。

  • 选择相邻的两个有序序列组成一个有序序列。

  • 重复第二步,直到全部组成一个有序序列。


Java版:

public static int[] mergeSort(int[] array, int start, int end) {
if (start == end) {
return new int[]{array[start]};
}
int mid = start + (end - start) / 2;
int[] leftArr = mergeSort(array, start, mid); //左有序数组
int[] rightArr = mergeSort(array, mid + 1, end); //右有序数组
int[] newNum = new int[leftArr.length + rightArr.length]; //新有序数组

int m = 0, i = 0, j = 0;
while (i < leftArr.length && j < rightArr.length) {
newNum[m++] = leftArr[i] < rightArr[j] ? leftArr[i++] : rightArr[j++];
}
while (i < leftArr.length) {
newNum[m++] = leftArr[i++];
}
while (j < rightArr.length) {
newNum[m++] = rightArr[j++];
}
return newNum;
}

8.基数分路排序

场景:对大批量数进行排序时。

  • 将所有的数的个位数取出,按照个位数进行排序,构成一个序列。

  • 将新构成的所有的数的十位数取出,按照十位数进行排序,构成一个序列。

  • 重复上述,直至最高位数为止。


Java版:

 public static void radixSort(int[] array, int d) //d表示最大的数有多少位
{
int k = 0;
int n = 1;
int m = 1; //控制键值排序依据在哪一位
int[][] temp = new int[10][array.length]; //数组的第一维表示可能的余数0-9
int[] order = new int[10]; //数组orderp[i]用来表示该位是i的数的个数
while(m <= d)
{
for(int i = 0; i < array.length; i++)
{
int lsd = ((array[i] / n) % 10);
temp[lsd][order[lsd]] = array[i];
order[lsd]++;
}
for(int i = 0; i < 10; i++)
{
if(order[i] != 0) {
for (int j = 0; j < order[i]; j++) {
array[k] = temp[i][j];
k++;
}
}
order[i] = 0;
}
n *= 10;
k = 0;
m++;
}
}


    总结:8种排序方法时间复杂度、空间复杂度,稳定性如下:


8种经典排序算法

8种经典排序算法


原文始发于微信公众号(码农吴先生):8种经典排序算法