面试中的 8 大排序算法总结
冒泡排序
冒泡排序是最简单的排序之一了，其大体思想就是通过与相邻元素的比较和交换来把小的数交换到最前面。这个过程类似于水泡向上升一样，因此而得名。
基本原理
将序列当中的左右元素，依次比较，如果左边的元素大于右边元素则交换位置，保证右边的元素始终大于左边的元素;( 第一轮结束后，序列最后一个元素一定是当前序列的最大值;)对序列当中剩下的n-1个元素再次执行步骤1。对于长度为n的序列，一共需要执行n-1轮比较。
代码实现：
/**
* 设置一个标志，如果这一趟发生了交换，则为true，否则为false。明显如果有一趟没有发生交换，说明排序已经完成。
* @param a
* @param n
*/
public class HelloWorld {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
//动态创建数组
int[] arr = new int[sc.nextInt()];
for(int i = 0 ; i< arr.length ; i++){
arr[i] = sc.nextInt();
}
/********** Begin **********/
boolean flag=true;
while(flag){
flag=false;
for(int i=0;i<arr.length-1;i++)
{
for(int j=0;j<arr.length-1-i;j++){
if(arr[j]>arr[j+1]){
int temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]= temp;
flag=true; //发生交换flag就为true。
}
}
}
}
System.out.print(Arrays.toString(arr));
/********** End **********/
}
}
选择排序
基本思想
给定一组记录，经过第一轮比较后得到最小的值，并将其与数组第一个位置的元素进行交换，接着从数组第二个位置的元素开始与其余元素比较，求出最大值，与数组第二个位置的元素交换位置，以此类推。直到只剩下一个元素不需要比较。
简单来说就说（ 遍历元素找到一个最小（或最大）的元素，把它放在第一个位置，然后再在剩余元素中找到最小（或最大）的元素，把它放在第二个位置，依次下去，完成排序。）
代码实现
public class HelloWorld {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
//动态创建数组
int[] arr = new int[sc.nextInt()];
for(int i = 0 ; i< arr.length ; i++){
arr[i] = sc.nextInt();
}
for(int i=0;i<arr.length-1;i++)
{
int flag=i;// 用来记录最大值的索引位置，默认值为i
for(int j=i+1;j<arr.length;j++)
{
if(arr[flag]<arr[j])
{
flag=j;
}
}
if(flag!=i){
int temp=arr[flag];
arr[flag]=arr[i];
arr[i]=temp;
}
}
System.out.println(Arrays.toString(arr));
}
}
插入排序
基本思想：
插入排序不是通过交换位置而是通过比较找到合适的位置插入元素来达到排序的目的的。相信大家都有过打扑克牌的经历，特别是牌数较大的。在分牌时可能要整理自己的牌，牌多的时候怎么整理呢？就是拿到一张牌，找到一个合适的位置插入。这个原理其实和插入排序是一样的。
举个栗子，对5,3,8,6,4这个无序序列进行简单插入排序，首先假设第一个数的位置时正确的，想一下在拿到第一张牌的时候，没必要整理。然后3要插到5前面，把5后移一位，变成3,5,8,6,4.想一下整理牌的时候应该也是这样吧。然后8不用动，6插在8前面，8后移一位，4插在5前面，从5开始都向后移一位。注意在插入一个数的时候要保证这个数前面的数已经有序。简单插入排序的时间复杂度也是O(n^2)。
代码实现
@Test
public void test3(){
int[] arr = new int[]{4,32,12,3,45,6};
int temp;
for(int i=1;i<arr.length;i++){
temp = arr[i];
int j;
for(j=i-1;j>=0;j--){
if(arr[j]>temp){
arr[j+1]=arr[j];
}else{
break;
}
}
arr[j+1]=temp;
//System.out.println(i+":"+ Arrays.toString(arr));
}
}
快速排序
基本原理：
快速排序一听名字就觉得很高端，在实际应用当中快速排序确实也是表现最好的排序算法
举个栗子：对5,3,8,6,4这个无序序列进行快速排序，思路是右指针找比基准数小的，左指针找比基准数大的，交换之。
5,3,8,6,4 用5作为比较的基准，最终会把5小的移动到5的左边，比5大的移动到5的右边。
5,3,8,6,4 首先设置i,j两个指针分别指向两端，j指针先扫描（思考一下为什么？）4比5小停止。然后i扫描，8比5大停止。交换i,j位置。
5,3,4,6,8 然后j指针再扫描，这时j扫描4时两指针相遇。停止。然后交换4和基准数。
4,3,5,6,8 一次划分后达到了左边比5小，右边比5大的目的。之后对左右子序列递归排序，最终得到有序序列。
上面留下来了一个问题为什么一定要j指针先动呢？首先这也不是绝对的，这取决于基准数的位置，因为在最后两个指针相遇的时候，要交换基准数到相遇的位置。一般选取第一个数作为基准数，那么就是在左边，所以最后相遇的数要和基准数交换，那么相遇的数一定要比基准数小。所以j指针先移动才能先找到比基准数小的数。
代码实现：
public class QuickSort {
public static void quickSort(int[] arr,int low,int high){
int i,j,temp,t;
if(low>high){
return;
}
i=low;
j=high;
//temp就是基准位
temp = arr[low];
while (i<j) {
//先看右边，依次往左递减
while (temp<=arr[j]&&i<j) {
j--;
}
//再看左边，依次往右递增
while (temp>=arr[i]&&i<j) {
i++;
}
//如果满足条件则交换
if (i<j) {
t = arr[j];
arr[j] = arr[i];
arr[i] = t;
}
}
//最后将基准为与i和j相等位置的数字交换
arr[low] = arr[i];
arr[i] = temp;
//递归调用左半数组
quickSort(arr, low, j-1);
//递归调用右半数组
quickSort(arr, j+1, high);
}
public static void main(String[] args){
int[] arr = {7,10,2,4,7,1,8,5,19};
quickSort(arr, 0, arr.length-1);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]+" ");
}
}
}
堆排序
“堆”这种数据结构，它是一种完全二叉树，也就是说除叶子节点外，其余节点全部是满数据的。
大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；
基本思想：
堆排序是借助堆来实现的选择排序，思想同简单的选择排序，以下以大顶堆为例。注意：如果想升序排序就使用大顶堆，反之使用小顶堆。原因是堆顶元素需要交换到序列尾部。
例如：将【5,1,3,7,9】这个无序序列进行堆排序：
首先，我们根据上述大根堆的定义将其构造成一个大根堆：
然后将根节点元素9和叶节点的末尾元素5进行交换，组成如下：
再将剩余的元素【5,7,3,1】重新构成一个大根堆：
然后将根节点元素7和叶节点的末尾元素1进行交换，组成如下：
再将剩余的元素【1,5,3】重新构成一个大根堆：
然后将根节点元素5和叶节点的末尾元素3进行交换，组成如下：
再将剩余的元素【3,1】重新构成一个大根堆：
然后将根节点元素3和叶节点的末尾元素1进行交换，组成如下：
这样就构成了一个有序序列。
代码实现：
public class HeapSort {
public static void main(String []args){
int []arr = {11,7,18,3,5,4,10,9};
sort(arr);
System.out.println(Arrays.toString(arr));
}
public static void sort(int []arr){
//1.构建大根堆
for(int i=arr.length/2-1;i>=0;i--){
//从第一个非叶子结点从下至上，从右至左调整结构
adjustHeap(arr,i,arr.length);
}
//2.调整堆结构+交换堆顶元素与末尾元素
for(int j=arr.length-1;j>0;j--){
swap(arr,0,j);//将堆顶元素与末尾元素进行交换
adjustHeap(arr,0,j);//重新对堆进行调整
}
}
/**
* 调整大顶堆（仅是调整过程，建立在大顶堆已构建的基础上）
* @param arr
* @param i
* @param length
*/
public static void adjustHeap(int []arr,int i,int length){
int temp = arr[i];//先取出当前元素i
for(int k=i*2+1;k<length;k=k*2+1){//从i结点的左子结点开始，也就是2i+1处开始
if(k+1<length && arr[k]<arr[k+1]){//如果左子结点小于右子结点，k指向右子结点
k++;
}
if(arr[k] >temp){//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
arr[i] = arr[k];
i = k;
}else{
break;
}
}
arr[i] = temp;//将temp值放到最终的位置
}
/**
* 交换元素
* @param arr
* @param a
* @param b
*/
public static void swap(int []arr,int a ,int b){
int temp=arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
}
希尔排序
基本原理
希尔排序是插入排序的一种高效率的实现，也叫缩小增量排序。基本思想是：先将整个待排记录序列分割成为若干子序列(不停的除以2取“间隔数”)分别进行直接插入排序，待整个序列中的记录基本有序时再对全体记录进行一次直接插入排序。
假如有一组数:【26, 53, 67, 48, 57, 13, 48, 32, 60, 50】，共10个元素，对其进行希尔排序；
先取第一个间隔数：10/2=5，从首元素开始，每隔5个元素取一个，组成组：
组成【26,13】，【53,48】，【67,32】，【48,60】，【57,50】；对这5个组分别进行插入排序：
为【13,26】，【48,53】，【32,67】，【48，60】，【50,57】；然后将它们放回到原来的位置，为：
【13, 48, 32, 48, 50, 26, 53, 67, 60, 57】；
然后取第二组间隔数：10/4=2，从首元素开始，每隔2个元素取一个，组成组：
组成【13,32,50,53,60】和【48,48,26,67,57】，然后对这两组数进行插入排序，为：
【13,32,50,53,60】和【26,48,48,57,67】；然后将它们放回到原来的位置，为：
【13,26,32,48,50,48,53,57,60,67】
然后取第三组间隔数：10/8=1，从首元素开始，每隔1个元素取一个，组成组，也就是典型的插入排序了，这里不画图演示了，排序结果为：【13 ，26， 32， 48， 48 ，50， 53， 57， 60， 67】
代码实现
/**
* 希尔排序
*/
@Test
public void test4(){
int[] data = new int[] {26, 53, 67, 48, 57, 13, 48, 32, 60, 50};
int j = 0;
int temp = 0;
for (int increment = data.length / 2; increment > 0; increment /= 2) {
System.out.println("increment:" + increment);
for (int i = increment; i < data.length; i++){
temp = data[i];
for (j = i - increment; j >= 0; j -= increment){
if (temp < data[j]){
data[j + increment] = data[j];
} else {
break;
}
}
data[j + increment] = temp;
}
for (int i = 0; i < data.length; i++){
System.out.print(data[i] + " ");
}
System.out.println();
}
}
归并排序
基本思想
这里我们说说归并排序，其最坏的时间维度是O(NlogN)，其思想是利用了“分治法”。
所谓的“分治法”即为：当一个大问题难以解决时，我们将其分为若干个小问题，然后将这些小问题解决了，那么大问题也就顺利解决了。那么怎么将其具体于排序上面呢？分两步：(1)拆分；(2)合并。
(1)拆分
当一组数据没法排序时，我们将其一分为二，发现他的一半还是没法排序，再将其一分为二，以此类推，直到分到只剩下一个元素为止，这样就好排序了，如下：
(2)组合
经过上述步骤，我们得到两组有序数组，在就是如何将这两组有序数组结合为一组有序数组，就ok了，不知道大家打过牌没有，假如有两副牌，他们都是从牌顶到牌底从小到大有序的，那我们如何将其组合成一副有序的牌组呢？我们先从两副牌顶各摸一张牌，并比较其大小，将小的放在手中，在以此类推，那么手中的牌就是这两副牌的有序数组了。
比如说，我们需要将上述最后两组数排序位一组有序数组：
首先比较arr[0]和brr[0]，arr[0]>brr[0]，那么我们将brr[0]的值放在crr[0]处：
再比较arr[0]和brr[1]，发现brr[1]>arr[0]，那么我们将arr[0]放在crr[1]处：
后面，以此类推：
代码实现
/**
* 归并排序
*/
public class MergerSort {
//临时数组，要定义成全局变量，不然在merge方法中每次递归都会创建一个数组，解决问题时候很容易超时！！
//我们一般都放入到不会递归的函数中去初始化
int[] tmp;
public static void main(String[] args) {
int[] arr = {24, 5, 98, 28, 99, 56, 34, 2, 11};
new MergerSort().MergeSort(arr);
System.out.print(Arrays.toString(arr));
}
private void MergeSort(int[] arr) {
tmp = new int[arr.length];
Sort(arr, 0, arr.length - 1);
}
/**
* 拆分
*
* @param a
* @param left
* @param right
*/
private void Sort(int[] a, int left, int right) {
if (left >= right) {
return;
}
int mid = left + (right - left) / 2;//从这里拆分
//二路归并排序里面有两个Sort，多路归并排序里面写多个Sort就可以了
Sort(a, left, mid);
Sort(a, mid + 1, right);
merge(a, left, mid, right);
}
/**
* 合并
*
* @param a
* @param left
* @param mid
* @param right
*/
private void merge(int[] a, int left, int mid, int right) {
int k = left;//存放指针
//下面这俩是检测指针
int p1 = left;//左边的起始索引
int p2 = mid + 1;//右边的起始索引
// 逐个归并
while (p1 <= mid && p2 <= right) {
if (a[p1] <= a[p2]) {
tmp[k++] = a[p1++];
} else {
tmp[k++] = a[p2++];
}
}
// //若左边序列还有剩余，则将其全部拷贝进tmp[]中：即将左边剩余的归并
while (p1 <= mid) {
tmp[k++] = a[p1++];
}
// 将右边剩余的归并
while (p2 <= right) {
tmp[k++] = a[p2++];
}
//将左右归并：存放入原数组
for (int i = left; i <= right; i++) {
a[i] = tmp[i];
}
}
}
基数排序
基本思想
基数排序不需要进行记录关键字之间的比较。基数排序是一种借助多关键字排序思想对单逻辑关键字进行排序的方法。所谓的多关键字排序就是有多个优先级不同的关键字。比如说成绩的排序，如果两个人总分相同，则语文高的排在前面，语文成绩也相同则数学高的排在前面。。。如果对数字进行排序，那么个位、十位、百位就是不同优先级的关键字，如果要进行升序排序，那么个位、十位、百位优先级一次增加。基数排序是通过多次的收分配和收集来实现的，关键字优先级低的先进行分配和收集。
代码实现
import java.util.Arrays;
public class MultiKeyRadixSortTest {
public static void main(String[] args) {
int[] data = new int[] { 1100, 192, 221, 12, 23 };
print(data);
radixSort(data, 10, 4);
System.out.println("排序后的数组：");
print(data);
}
public static void radixSort(int[] data, int radix, int d) {
// 缓存数组
int[] tmp = new int[data.length];
// buckets用于记录待排序元素的信息
// buckets数组定义了max-min个桶
int[] buckets = new int[radix];
for (int i = 0, rate = 1; i < d; i++) {
// 重置count数组，开始统计下一个关键字
Arrays.fill(buckets, 0);
// 将data中的元素完全复制到tmp数组中
System.arraycopy(data, 0, tmp, 0, data.length);
// 计算每个待排序数据的子关键字
for (int j = 0; j < data.length; j++) {
int subKey = (tmp[j] / rate) % radix;
buckets[subKey]++;
}
for (int j = 1; j < radix; j++) {
buckets[j] = buckets[j] + buckets[j - 1];
}
// 按子关键字对指定的数据进行排序
for (int m = data.length - 1; m >= 0; m--) {
int subKey = (tmp[m] / rate) % radix;
data[--buckets[subKey]] = tmp[m];
}
rate *= radix;
}
}
public static void print(int[] data) {
for (int i = 0; i < data.length; i++) {
System.out.print(data[i] + "\t");
}
System.out.println();
}
}
总结
