# 常用排序算法代码兑现

01

1. 各种排序算法的时间、空间复杂度；
2. 算法的稳定性；
3. 算法的优化改进
4. 算法的应用场景

02

//swap element at i to at j private static void swap(int[] array, int i,int j){ int tmp = array[i]; array[i] = array[j]; array[j] = tmp; }

1. array： 待排序的数组，类型为一维整形数组
2. n：元素个数
3. i：一般为外层循环索引，或表示排序区或未排序的开始或结束索引
4. j ：一般为内层循环索引，或表示未排序区或排序的结束或开始索引
5. lo：数组计算区间的开始索引
6. hi：数组计算区间的结束索引
7. d ：分组长度
8. k：分组索引

03

//bubble sort public static void bubbleSort(int[] array, int n){ int i = 0;// loop int j = 0; // element index while(i < n) { for(j=0; j<n-i-1; j++){ if( array[j] > array[j+1] ){ //swap condition swap( array, j, j +1 ); } } i++; } }

04

//quick sort public static void quickSort(int[] array, int lo, int hi){ if(lo>hi) return; int pivot = array[lo]; int i = lo; int j = hi; while( i<j ){ //get smaller after pivot //warning: while condition, here and next while //at least one item is >= while(i < j && array[j] >= pivot){ j--; } array[i] = array[j]; //so at j an element is void //get bigger before pivot while(i < j && array[i] < pivot){ i++; } array[j] = array[i]; // at i an element is to fill at j } //here, i bumps into j array[i] = pivot; //here, before index i smaller than pivot, after bigger than pivot // lo~i quick sort quickSort(array, lo, i-1); // i+1~hi quick sort quickSort(array, i+1, hi); }

05

//direct select sort public static void selectSort(int[] array, int n){ int i=0; //sorted last element int j=0; //unsorted first element while(i<n){ int min=array[i]; int index = i; for(j=i+1; j<n;j++){ if(array[j]<min){ min = array[j]; index = j; } } swap(array,i,index); i++; } }

06

1. 构建堆函数，左右子节点可能都有，也可能只含有左节点，咖啡色标记的代码
2. 堆排序函数，while遍历时，buildHeap参数中元素个数每次减1，始终从位置0（堆顶）开始调整。

//heap sort public static void heapSort(int[] array, int n){ for (int i = n / 2 - 1; i >= 0; i--) buildHeap(array, n, i); int len = n - 1; while (len > 0) { swap(array, 0, len); buildHeap(array, len, 0); len--; } } private static void buildHeap(int[] array, int n, int i){ for (; left(i) < n; i = left(i)) { int bigger = right(i) < n ? max(array, left(i), right(i)) : left(i); if (array[bigger] > array[i]) //swap swap(array, bigger, i); else break; } } private static int left(int i){ return 2*i+1; } private static int right(int i){ return 2*i+2; } private static int max(int[] array, int i, int j){ return array[i]>array[j]? i:j; }

07

// insert sort public static void insertSort(int[] array, int n){ int i = 1; //unsorted first index while (i < n) { int j = i - 1; //sorted last index int insert = array[i]; //warning: label array[i] while (j > 0 && insert < array[j]){ array[j + 1] = array[j]; j--; } array[j + 1] = insert; //j+1 is insert pos i++; } }

08

//shell Sort public static void shellSort(int[] array, int n, int group){ if (group > n) return; int d = n / group; //d: number for each group while (d > 0){ for (int i = 0; i < d; i++){ int j = i; // number index int k = 1; //distance index while (j < n){ int insert = array[j]; //label unsorted first j -= d; //sorted last index while (j > 0 && insert < array[j]){ array[j + d] = array[j]; j -= d; } array[j + d] = insert; //insert pos: j+d j = i + (++k) * d; //next number index } } d /= 2; } }

09

//merge sort public static void mergeSort(int[] array, int n){ var sorted = new int[n]; mergeSort(array,sorted,0,n-1); } private static void mergeSort(int[] array, int[] sorted, int lo, int hi){ if (lo < hi){ int mid = lo + (hi - lo) / 2; mergeSort(array, sorted,lo, mid); mergeSort(array, sorted, mid + 1, hi); merge(array, sorted, lo, mid, hi); } } //beg: part1 beginning index //mid: part1 end index //mid+1: part2 beginning index //end: part2 end index private static void merge(int[] array, int[] sorted, int beg, int mid, int end){ int i = beg; //part1 index int j = mid + 1; //part2 index int k = 0; //merged index while (i <= mid && j <= end) sorted[k++] = array[i] <= array[j] ? array[i++] : array[j++]; while (i <= mid) sorted[k++] = array[i++]; while (j <= end) sorted[k++] = array[j++]; for (i = 0; i < k; i++) array[beg + i] = sorted[i]; }

10

0 条评论

• ### 一起来用python实现一下十大经典排序算法

既然之前很多小伙伴反应希望公众号多发点算法类的文章，那就来呗。先从简单的入手好了，带大家用python来实现一波十大经典排序算法呗。分别是：

• ### 1800字普林斯顿大学课程浓缩笔记：程序员必知的算法之查找和排序算法

老生常谈，偶尔遇到阐述这两类问题相关的极好素材，它们结合示意图，言简意赅，清晰明了。故分享出来。

• ### 漫画：最最最最最简单的选择排序

当我们用到它的时候，数据规模越小越好，不会占用额外的内存空间并且运行时间与输入无关。理论上讲，选择排序可能也是平时排序一般人想到的最多的排序方法了吧。

• ### 算法笔记之排序

最近在看《算法笔记》，如果单从算法来说，这本书真正做到了短小精悍，首先以排序入题，那么我们今天也来说说排序。 排序 将一堆杂乱无章的元素按照某种规则有序排列的过...

• ### Java数据结构和算法（三）——冒泡、选择、插入排序算法

上一篇博客我们实现的数组结构是无序的，也就是纯粹按照插入顺序进行排列，那么如何进行元素排序，本篇博客我们介绍几种简单的排序算法。 1、冒泡排序 　　这个名词...

• ### 浅谈 Integer 类

突然发现自己对Integer i = 10;这种语法不太明白，于是乎有了这篇文章，那么在讲解 Integer 之前，我们先看下面这段代码： public s...

• ### 冒泡排序法三部曲终极版の最优的冒泡排序算法

对于数组{1,2,5,9,4,10,13,59,30}每进行一次排序，右侧的有效位就会加一，可是在之前的两种方法中，每次小循环的比较次数依然是数组长度-1。

• ### 如何用 Java 实现十大经典排序算法？

最近几天在研究排序算法，看了很多博客，发现网上有的文章中对排序算法解释的并不是很透彻，而且有很多代码都是错误的，例如有的文章中在“桶排序”算法中对每个桶进行排序...

• ### 面试常问的十个排序算法都在这里了（含JAVA代码实现）

ps：上篇的动图数据结构反响不错，这次来个动图排序算法大全。数据结构与算法，齐了。