这里将列举知名度较高的十种算法，附上自己的理解和代码。
- 冒泡排序
- 选择排序
- 插入排序
- 希尔排序
- 归并排序
- 快速排序
- 堆排序
- 计数排序
- 桶排序
- 基数排序
启发和图片来自 十大经典排序算法（动图演示）
先来理解两个概念：时间复杂度与空间复杂度
他俩是相互对立的，时间复杂度的减小必然伴随空间复杂度的增加，所以算法的选择也是时间与空间的取舍。
冒泡排序
理解：从左至右顺序判断当前气泡是否大于后一个气泡，将大气泡右移。
内循环，将较大的气泡向后移，保证了内循环的当前值比前面的所有值都大。（冒泡的过程，一步一步的移动）
外循环第一次，扫描出数组中的最大值并逐个的交换到数组最末端。
外循环第二次，扫描出数组中的次最大值并逐个的交换到数组次末端。
public String sort(int[] numbers) {
long stamp = System.currentTimeMillis();
for (int i = 0; i < numbers.length; i++) {
for (int j = 0; j < numbers.length - 1 - i; j++) {
if (numbers[j] > numbers[j + 1]) {
Utils.swap(numbers, j, j + 1);
}
}
}
return Utils.intsToString(numbers) + " cost:" + (System.currentTimeMillis() - stamp);
}
时间空间复杂度：O(n2)、O(0) （取决于Utils.swap(numbers, j, j + 1)是哪种交换方式）
选择排序
理解：在未排序的部分，每次选择一个最小的交换到未排序的头项。
public String sort(int[] numbers) {
long stamp = System.currentTimeMillis();
for (int i = 0; i < numbers.length - 1; i++) {
int position=i;
for (int j = i + 1; j < numbers.length; j++) {
if (numbers[j]<numbers[position]){
position=j;
}
}
Utils.swap(numbers,i,position);
}
return Utils.intsToString(numbers) + " cost:" + (System.currentTimeMillis() - stamp);
}
时间空间复杂度：O(n2)、O(0)
*蹩脚的选择排序
没写这篇文章之前我一直用的是这种排序：
for (int i = 0; i < numbers.length - 1; i++) {
for (int j = i + 1; j < numbers.length; j++) {
if (numbers[j] < numbers[i]) {
Utils.swap(numbers, i, j);//正规的是记录最小位置
}
}
//在内循环完成后再交换，这样可以减少交换次数
}
很像，但是这种排序把选择的功能弱化了，增加了交换的次数。
插入排序
理解：选取一项，如果小于前一项，将前一项后移，操作往复，直到前一项小于它，将选取的项放在当前位置（当前位置项已被后移）
public String sort(int[] numbers) {
long stamp = System.currentTimeMillis();
for (int i = 1; i < numbers.length; i++) {
int prePosition = i - 1;
int current = numbers[i];
while (prePosition >= 0 && current < numbers[prePosition]) {
numbers[prePosition + 1] = numbers[prePosition];
prePosition--;
}
numbers[prePosition + 1] = current;
}
return Utils.intsToString(numbers) + " cost:" + (System.currentTimeMillis() - stamp);
}
时间空间复杂度：O(n2)、O(1)
希尔排序
理解：
设定一个间隔gap，对按gap组成的新数组进行排序；
对gap设置一个递减规则，直到1；
gap每次变化后执行第一步；
public String sort(int[] data) {
long stamp = System.currentTimeMillis();
for (int gap = data.length / 2; gap > 0; gap /= 2) {
for (int i = gap; i < data.length; i++) {
int temp = data[i];
int j;
for (j = i - gap; j >= 0; j -= gap) {
if (temp < data[j]) {
data[j + gap] = data[j];//交换的话会有很多次
} else {
break;//之前的已经排好序了，继续循环也没意义
}
}
data[j + gap] = temp;
}
}
return Utils.intsToString(data) + " cost:" + (System.currentTimeMillis() - stamp);
}
时间空间复杂度：O(n2)、O(1) 三层for并不是3次方，因为每层for不全为n
归并排序
理解：将数组中间切开直到不可切，然后按每次翻倍的规律（1-1、2-2、4-4、8-8），按大小合并。最后一次合并为排好序的数组。
private int[] mergeSort(int[] numbers) {
int len = numbers.length;
if (len < 2) {
return numbers;
}
int middle = len / 2;
int[] left = new int[middle];
int[] right = new int[len - middle];
System.arraycopy(numbers, 0, left, 0, middle);
System.arraycopy(numbers, middle, right, 0, numbers.length - middle);
return merge(mergeSort(left), mergeSort(right));
}
private int[] merge(int[] left, int[] right) {
int[] result = new int[left.length + right.length];
int leftP = 0;
int rightP = 0;
int resultP = 0;
while (leftP < left.length && rightP < right.length) {
if (left[leftP] > right[rightP]) {
result[resultP++] = right[rightP++];
} else if (left[leftP] < right[rightP]) {
result[resultP++] = left[leftP++];
} else {
result[resultP++] = left[leftP++];
result[resultP++] = right[rightP++];
}
}
while (leftP < left.length) {
result[resultP++] = left[leftP++];
}
while (rightP < right.length) {
result[resultP++] = right[rightP++];
}
return result;
}
时间空间复杂度：O(nlog2n)、O(n)
快速排序
理解：选取一个基准值，将该基准值所在数组中的排序位置找到。循环选取基准值，直到数组中所有值都充当过基准值，则数组排序完成。
private void quickSort(int[] numbers, int left, int right) {
int partitionIndex;
if (left < right) {
partitionIndex = partition(numbers, left, right);
quickSort(numbers, left, partitionIndex - 1);
quickSort(numbers, partitionIndex + 1, right);
}
}
private int partition(int[] numbers, int left, int right) {
int pivot = left;
int index = pivot + 1;
for (int i = index; i <= right; i++) {
if (numbers[i] < numbers[pivot]) {
Utils.swap(numbers, i, index++);
}
}
Utils.swap(numbers, pivot, index - 1);
return index - 1;
}
时间空间复杂度：O(n2)、O(nlog2n)（nlog2n为交换时产生的临时变量，可通过加减交换减少空间复杂度）
堆排序
先前知识
堆
一颗完全二叉树，其非叶子节点必须大于（或小于）其叶子节点
大顶堆
非叶子节点大于其叶子节点的称为大顶堆
小顶堆
非叶子节点小于于其叶子节点的称为小顶堆
理解：利用大顶堆的特性，上一层的节点必定大于下一层节点。
取根节点（最大值）与最后一个叶子节点交换，将剩下的节点按大顶堆的性质重新排序。重复此操作，可得到由小到大的排好序的数组。
public String sort(int[] numbers) {
long stamp = System.currentTimeMillis();
len=numbers.length;
for (int i = numbers.length / 2; i >= 0; i--) {//生成大顶堆
adjustHeap(numbers, i);
}
for (int i = numbers.length-1; i >=0 ; i--) {
Utils.swap(numbers,0,i);
len--;
adjustHeap(numbers,0);
}
return Utils.intsToString(numbers) + " cost:" + (System.currentTimeMillis() - stamp);
}
int len;
private void adjustHeap(int[] numbers, int p) {
int left = p * 2 + 1;
int right = p * 2 + 2;
int bigP = p;
if (left < len && numbers[left] > numbers[bigP]) {
bigP = left;
}
if (right < len && numbers[right] > numbers[bigP]) {
bigP = right;
}
if (p != bigP) {
Utils.swap(numbers, p, bigP);
adjustHeap(numbers, bigP);
}
}
时间空间复杂度：O(nlog2n)、O(0)由交换方法决定
计数排序
理解：计数排序适用于数据范围密集的集合。
建立一个临时数组（数据范围）用于存放数据，临时数组的下标代表数据值，临时数组的值代表数据出现的次数。数据按规则全部放到临时数组后，按临时数组下标全部取出数据，即为排好序的数组。
public String sort(int[] numbers) {
long stamp = System.currentTimeMillis();
int[] result = new int[numbers.length];
int max = numbers[0], min = numbers[0];
for (int number : numbers) {
if (number > max) {
max = number;
}
if (number < min) {
min = number;
}
}
int[] temp = new int[max - min + 1];
for (int i = 0; i < numbers.length; i++) {
temp[numbers[i] - min]++;
}
int p=0;
for (int i = 0; i <temp.length ; i++) {
while (temp[i]>0){
result[p++]=i+min;
temp[i]--;
}
}
return Utils.intsToString(result) + " cost:" + (System.currentTimeMillis() - stamp);
}
时间空间复杂度：O(n+k)、O(n+k) k表示范围数组的大小
桶排序
理解：计数排序是桶排序的一种特例，计数排序每个桶内放的数据都是相同的，排序时只需按桶的顺序倒出即可得到排好序的数组；而桶排序每个桶内的数据不相同，需要对桶内数据排序，然后按桶的顺序倒出才能得到排好序的数组；
public String sort(int[] numbers) {
long stamp = System.currentTimeMillis();
int max = numbers[0];
int min = numbers[0];
for (int number : numbers) {
if (number > max) {
max = number;
}
if (number < min) {
min = number;
}
}
int bucketNum = (max - min) / numbers.length + 1;
ArrayList<ArrayList<Integer>> buckets = new ArrayList<ArrayList<Integer>>();
for (int i = 0; i < bucketNum; i++) {
buckets.add(new ArrayList<Integer>());
}
for (int i = 0; i < numbers.length; i++) {
int p = (numbers[i] - min) / numbers.length;
buckets.get(p).add(numbers[i]);
}
for (int i = 0; i < buckets.size(); i++) {
Collections.sort(buckets.get(i));
}
return buckets.toString() + " cost:" + (System.currentTimeMillis() - stamp);
}
时间空间复杂度：O(n)、O(n)
基数排序
理解：所有数字都是由0-9组成，大小的比较也是位数与每位上的数字的比较。
先按个位数字大小将数组排序、然后按十位数字大小将数组排序，位数一直增加，直到数组内最大项的位数。
public String sort(int[] numbers) {
long stamp = System.currentTimeMillis();
ArrayList<ArrayList<Integer>> temp = new ArrayList<ArrayList<Integer>>();
int max = numbers[0];
int radix = 10;
for (int i = 0; i < 10; i++) {
temp.add(i, new ArrayList<Integer>());
}
do {
for (int i = 0; i < numbers.length; i++) {
if (numbers[i] > max) {
max = numbers[i];
}
temp.get(numbers[i] % radix / (radix / 10)).add(numbers[i]);
}
int p = 0;
for (int i = 0; i < temp.size(); i++) {
for (int j = 0; j < temp.get(i).size(); j++) {
numbers[p++] = temp.get(i).get(j);
}
temp.get(i).clear();
}
radix *= 10;
} while (radix < max * 10);
return Utils.intsToString(numbers) + " cost:" + (System.currentTimeMillis() - stamp);
}
时间空间复杂度：O(nk)、O(n+k) 有些说法是空间复杂度为O(n)那是对n取了极限
此外还有一家公司的上机题：为String中char出现的次数排序，相同次数的按字典排序。
此题就不写了，此题和上述十种排序算法的代码在GitHub
网友评论