JAVA春招必背面试题-数据结构&算法-排序&散列表

5、排序

一、排序方法与复杂度归类
（1）几种最经典、最常用的排序方法：冒泡排序、插入排序、选择排序、快速排序、归并排序、计数排序、基数排序、桶排序。
（2）复杂度归类
冒泡排序、插入排序、选择排序 O(n^2)
快速排序、归并排序 O(nlogn)
计数排序、基数排序、桶排序 O(n)

二、如何分析一个“排序算法”？
<1>算法的执行效率

1. 最好、最坏、平均情况时间复杂度。
2. 时间复杂度的系数、常数和低阶。
3. 比较次数，交换（或移动）次数。
   <2>排序算法的稳定性
4. 稳定性概念：如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。
5. 稳定性重要性：可针对对象的多种属性进行有优先级的排序。
6. 举例：给电商交易系统中的“订单”排序，按照金额大小对订单数据排序，对于相同金额的订单以下单时间早晚排序。用稳定排序算法可简洁地解决。先按照下单时间给订单排序，排序完成后用稳定排序算法按照订单金额重新排序。
   <3>排序算法的内存损耗
   原地排序算法：特指空间复杂度是O(1)的排序算法。

冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求，如果不满足就让它俩互换。

代码:

public int[] bubbleSort(int[] a) {
int n = a.length;
if (n<=1) {
return a;
}
for (int i = 0; i < n; i++) {
//提前退出冒泡循环的标志
boolean flag = false;
for (int j = 0; j < n-i-1; j++) {
if (a[j]>a[j+1]) {//
int temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;

                flag = true;//表示有数据交换
            }
            if (!flag) {
                break; //没有数据交换(说明已排好序无需再进行冒泡),提前退出
            }
        }
    }
    return a;
}

插入排序将数组数据分成已排序区间和未排序区间。初始已排序区间只有一个元素，即数组第一个元素。在未排序区间取出一个元素插入到已排序区间的合适位置，直到未排序区间为空。

代码:

public int[] insertionSort(int[] a) {
    int n = a.length;
    if (n<=1) return a;

    for (int i = 1; i < n; i++) {
        int value = a[i];
        int j = i-1;
        for (; j >=0; j--) {
            if (a[j] > value) {
                a[j+1] = a[j];//移动数据
            }else {
                break;
            }
        }
        a[j+1] = value;//插入数据
    }

    return a;
}

选择排序将数组分成已排序区间和未排序区间。初始已排序区间为空。每次从未排序区间中选出最小的元素插入已排序区间的末尾，直到未排序区间为空。
代码:

public int[] selectionSort(int[] a) {
int n = a.length;

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

    return a;
}

如果要排序一个数组,我们先把数组从中间分成前后两部分,然后对前后两部分分别排序,再将排好序的两部分合并在一起,这样整个数组就都有序了。

实现思路:

merge-sort(p...r)表示,给下标从p到r之间的数组排序。我们将这个排序问题转化为了两个子问 ,题, merge_sort(p...q)和merge-sort(q+1..r),其中下标q等于p和r的中间位置,也就是, (p+r)/2,当下标从p到q和从q+1到r这两个子数组都排好序之后,我们再将两个有序的子数组合并在一起,这样下标从p到r之间的数据就也排好序了。

代码:

// 归并排序算法, a是数组，n表示数组大小
public static void mergeSort(int[] a, int n) {
mergeSortInternally(a, 0, n-1);
}

// 递归调用函数
private static void mergeSortInternally(int[] a, int p, int r) {
// 递归终止条件
if (p >= r) return;

// 取p到r之间的中间位置q
int q = (p+r)/2;
// 分治递归
mergeSortInternally(a, p, q);
mergeSortInternally(a, q+1, r);

// 将A[p...q]和A[q+1...r]合并为A[p...r]
merge(a, p, q, r);

}

private static void merge(int[] a, int p, int q, int r) {
int i = p;
int j = q+1;
int k = 0; // 初始化变量i, j, k
int[] tmp = new int[r-p+1]; // 申请一个大小跟a[p...r]一样的临时数组

// 1 排序
while (i<=q && j<=r) {
  if (a[i] <= a[j]) {
    tmp[k++] = a[i++]; // i++等于i:=i+1
  } else {
    tmp[k++] = a[j++];
  }
}

// 2 判断哪个子数组中有剩余的数据
int start = i;
int end = q;
if (j <= r) {
  start = j;
  end = r;
}

// 3 将剩余的数据拷贝到临时数组tmp
while (start <= end) {
  tmp[k++] = a[start++];
}

// 4 将tmp中的数组拷贝回a[p...r]
for (i = 0; i <= r-p; ++i) {
  a[p+i] = tmp[i];
}

}

七、快速排序

快排的思想: 如果要排序数组中下标从p到r之间的一组数据,我们选择p到r之间的任意一个数据作为pivot (分区点) 。我们遍历p到r之间的数据,将小于pivot的放到左边,将大于pivot的放到右边,将pivot放到中间。经过这一步骤之后,数组p到r之间的数据就被分成了三个部分,前面p到q-1之间都是小于pivot的,中间是pivot,后面的q+1到r之间是大于pivot的。

八、线性排序:
时间复杂度O(n)

我们把时间复杂度是线性的排序算法叫作线性排序(Linear sort)常见的线性算法有: 桶排序、计数排序、基数排序

特点:

非基于比较的排序算法

桶排序

桶排序,顾名思义,会用到“桶" ,核心思想是将要排序的数据分到几个有序的桶里,每个桶里的数据再单独进行排序。桶内排完序之后,再把每个桶里的数据按照顺序依次取出,组成的序列就是有序的了。

对排序的数据要求苛刻:

1, 要排序的数据需要很容易就能划分成m个桶,并且,桶与桶之间有着天然的大小顺序。

2 ,数据在各个桶之间的分布是比较均匀的。

计数排序

计数排序只能用在数据范围不大的场景中,如果数据范围k比要排序的数据n大很多,就不适合用计数排序了。

计数排序只能给非负整数排序,如果要排序的数据是其他类型的,要将其在不改变相对大小的情况下,转化为非负整数。

代码:

// 计数排序，a是数组，n是数组大小。假设数组中存储的都是非负整数。
public static void countingSort(int[] a) {
int n = a.length;
if (n <= 1) return;

// 查找数组中数据的范围
int max = a[0];
for (int i = 1; i < n; ++i) {
  if (max < a[i]) {
    max = a[i];
  }
}

// 申请一个计数数组c，下标大小[0,max]
int[] c = new int[max + 1];
for (int i = 0; i < max + 1; ++i) {
  c[i] = 0;
}

// 计算每个元素的个数，放入c中
for (int i = 0; i < n; ++i) {
  c[a[i]]++;
}

// 依次累加
for (int i = 1; i < max + 1; ++i) {
  c[i] = c[i-1] + c[i];
}

// 临时数组r，存储排序之后的结果
int[] r = new int[n];
// 计算排序的关键步骤了，有点难理解
for (int i = n - 1; i >= 0; --i) {
  int index = c[a[i]]-1;
  r[index] = a[i];
  c[a[i]]--;
}

// 将结果拷贝会a数组
for (int i = 0; i < n; ++i) {
  a[i] = r[i];
}