本文介绍一些经典的排序、查找算法。
(1)冒泡排序
对大小为N的数组进行冒泡排序，要进行(N-1)轮比较，每一轮将一个最大数移至数组的最后一个位置，就像是冒泡一样。
时间复杂度：O(N)
Java版本：
void bubbleSort(int[] a) {
for (int i = 1; i < a.length; i++) {
for (int j = 0; j < a.length - i; j++) {
if (a[j] > a[j + 1]) {
int tmp = a[j];
a[j] = a[j + 1];
a[j + 1] = tmp;
}
}
}
}
Kotlin版本：
fun bubbleSort(a: IntArray) {
for (i in 1 until a.size) {
for (j in 0 until a.size - i) {
if (a[j] > a[j + 1]) {
val tmp = a[j]
a[j] = a[j + 1]
a[j + 1] = tmp
}
}
}
}
(2)选择排序
主要思路：首先，找到一个最小值，将它与第一个位置的元素交换；接着从n-1个数据中找到最小的，与第二个位置的元素交换；然后，不断重复这个过程，直到最后两个数据处理完。
时间复杂度：O(N)
Java版本：
void selectSort(int[] a){
int index , tmp;
for (int i =0;i<a.length-1;i++){
index = i;
for (int j = i+1;j<a.length;j++){
if (a[j] < a[index]){
index = j;
}
}
if (index != i){
tmp = a[index];
a[index] = a[i];
a[i] = tmp;
}
}
}
Kotlin版本：
fun selectSort(a: IntArray) {
var index: Int
var tmp: Int
for (i in 0 until a.size - 1) {
index = i
for (j in i + 1 until a.size) {
if (a[j] < a[index]) {
index = j
}
}
if (index != i) {
tmp = a[index]
a[index] = a[i]
a[i] = tmp
}
}
}
(3)插入排序
基本思路：从第1个数据起，将它与前面的数据比较，然后插入适当位置。
时间复杂度：O(N)
Java版本：
void insertSort(int[] a) {
int j, tmp;
for (int i = 1; i < a.length; i++) {
j = i - 1;
tmp = a[i];
while (j >= 0 && tmp < a[j]) {
a[j + 1] = a[j];
j--;
}
a[j + 1] = tmp;
}
}
Kotlin版本：
fun insertSort(a: IntArray) {
var j: Int
var tmp: Int
for (i in 1 until a.size) {
j = i - 1
tmp = a[i]
while (j >= 0 && tmp < a[j]) {
a[j + 1] = a[j]
j--
}
a[j + 1] = tmp
}
}
(4)Shell排序
基本思路：先将N个元素分为N/2个组，每组为一对；一次循环，使每组排好顺序；然后，在分为N/4个组，再次排序；不断重复这个过程，直到最后变成一个组，也就完成了排序。
时间复杂度：O(N logN)
Java版本：
void shellSort(int[] a) {
int i, j;
int groupN, tmp;
for (groupN = a.length / 2; groupN >= 1; groupN /= 2) {
for (i = groupN; i < a.length; i++) {
tmp = a[i];
j = i - groupN;
while (j >= 0 && tmp < a[j]) {
a[j + groupN] = a[j];
j -= groupN;
}
a[j + groupN] = tmp;
}
}
}
Kotlin版本：
fun shellSort(a: IntArray) {
var i: Int
var j: Int
var groupN: Int
var tmp: Int
groupN = a.size / 2
while (groupN >= 1) {
i = groupN
while (i < a.size) {
tmp = a[i]
j = i - groupN
while (j >= 0 && tmp < a[j]) {
a[j + groupN] = a[j]
j -= groupN
}
a[j + groupN] = tmp
i++
}
groupN /= 2
}
}
(5)快速排序
基本思路：首先设置一个分界值，它将数组分割成两部分；将大于分界值的数据集中到数组右边，小于分界值的数据集中到左边；然后左右两边的数组独立排序，重复这个过程直到结束。
时间复杂度：O(N logN)
Java版本如下：
public static void quickSort(int[] a, int low, int high) {
int i, j, pivot;
//结束条件
if (low >= high) {
return;
}
i = low;
j = high;
//选择基准点
pivot = a[low];
while (i < j) {
//从左往右找比节点大的数，循环结束要么找到了，要么i=j
while (a[i] <= pivot && i < j) {
i++;
}
//从右往左找比节点小的数，循环结束要么找到了，要么i=j
while (a[j] >= pivot && i < j) {
j--;
}
//如果i!=j说明都找到了，就交换这两个数
if (i < j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
//将基准点插入到对应位置
a[low] = a[i];
a[i] = pivot;
//数组“分两半”,再重复上面的操作
quickSort(a, low, i - 1);
quickSort(a, i + 1, high);
}
Kotlin版本：
fun quickSort(a: IntArray, low: Int, high: Int) {
var i: Int
var j: Int
val pivot: Int
//结束条件
if (low >= high) {
return
}
i = low
j = high
//选择基准点
pivot = a[low]
while (i < j) {
//从左往右找比节点大的数，循环结束要么找到了，要么i=j
while (a[i] <= pivot && i < j) {
i++
}
//从右往左找比节点小的数，循环结束要么找到了，要么i=j
while (a[j] >= pivot && i < j) {
j--
}
//如果i!=j说明都找到了，就交换这两个数
if (i < j) {
val temp = a[i]
a[i] = a[j]
a[j] = temp
}
}
//将基准点插入到对应位置
a[low] = a[i]
a[i] = pivot
//数组“分两半”,再重复上面的操作
quickSort(a, low, i - 1)
quickSort(a, i + 1, high)
}
(6)堆排序
思路：使用堆结构来实现排序（堆是一种完全二叉树，大根堆即节点数据比左右子孩子数据大）；先将原始数组构建成一个大根堆，然后将第一个元素与最后一个元素交换；交换可能破坏了大根堆的结构，接着将剩下的n-1个元素组成的数组调整为一个大根堆，不断重复这个过程直到结束。
时间复杂度：O(N logN)
Java版本：
public static void heapSort(int[] arr){
//为什么从arr.length/2-1开始？因为这是最后一个非叶节点
for (int i = arr.length/2-1; i >= 0 ; i--) {
adjustHeap(arr,i,arr.length);
}
for (int j = arr.length-1; j > 0; j--) {
//将第一个元素与最后一个元素交换，然后使得剩下的n-1个元素组成大根堆
int temp = arr[j];
arr[j] = arr[0];
arr[0] = temp;
adjustHeap(arr,0,j);
}
}
/**
* 将以i为节点的子树调整为大根堆结构
*/
public static void adjustHeap (int[] arr,int i,int length){
int temp = arr[i];
/*j=i*2+1表示的是i结点的左子结点*/
for (int j = i * 2 + 1; j < length ; j = j * 2 + 1) {
if (j+1 < length && arr[j] < arr[j+1]){ //左子结点小于右子结点
j++; //j指向右子结点
}
if (arr[j] > temp){ //子节点大于父节点
arr[i] = arr[j]; //把较大的值赋值给父节点
i = j; //让i指向与其换位的子结点
}else{
/*子树已经是大顶堆了*/
break;
}
}
arr[i] = temp;
}
Kotlin版本：
fun heapSort(arr: IntArray) {
//为什么从arr.size/2-1开始？因为这是最后一个非叶节点
for (i in arr.size / 2 - 1 downTo 0) {
adjustHeap(arr, i, arr.size)
}
for (j in arr.size - 1 downTo 1) {
//将第一个元素与最后一个元素交换，然后使得剩下的n-1个元素组成大根堆
val temp = arr[j]
arr[j] = arr[0]
arr[0] = temp
adjustHeap(arr, 0, j)
}
}
/**
* 将以i为节点的子树调整为大根堆结构
*/
fun adjustHeap(arr: IntArray, i: Int, length: Int) {
var i = i
val temp = arr[i]
/*j=i*2+1表示的是i结点的左子结点*/
var j = i * 2 + 1
while (j < length) {
if (j + 1 < length && arr[j] < arr[j + 1]) { //左子结点小于右子结点
j++ //j指向右子结点
}
if (arr[j] > temp) { //子节点大于父节点
arr[i] = arr[j] //把较大的值赋值给父节点
i = j //让i指向与其换位的子结点
} else {
/*子树已经是大顶堆了*/
break
}
j = j * 2 + 1
}
arr[i] = temp
}
(7)归并排序
思路：算法的基本操作是合并两个已经排好序的表；因为已经排好序，所以将输出放到第三个表中，只需对输入数据进行一趟排序即可。
时间复杂度：O(N logN)
Java版本：
static void mergeSort(int[] a) {
int[] tmp = new int[a.length];
mergeSort(a, tmp, 0, a.length - 1);
}
static void mergeSort(int[] a, int[] tmpArray, int left, int right) {
if (left < right) {
int center = (left + right) / 2;
mergeSort(a, tmpArray, left, center);
mergeSort(a, tmpArray, center + 1, right);
merge(a, tmpArray, left, center + 1, right);
}
}
static void merge(int[] a, int[] tmpArray, int leftPos, int rightPos, int rightEnd) {
int leftEnd = rightPos - 1;
int tmpPos = leftPos;
int num = rightEnd - leftPos + 1;
while (leftPos <= leftEnd && rightPos <= rightEnd) {
if (a[leftPos] < a[rightPos]) {
tmpArray[tmpPos++] = a[leftPos++];
} else {
tmpArray[tmpPos++] = a[rightPos++];
}
}
//左边还有剩余，copy
while (leftPos <= leftEnd) {
tmpArray[tmpPos++] = a[leftPos++];
}
//右边还有剩余，copy
while (rightPos <= rightEnd) {
tmpArray[tmpPos++] = a[rightPos++];
}
//将tmpArray copy back
for (int i = 0; i < num; i++, rightEnd--) {
a[rightEnd] = tmpArray[rightEnd];
}
}
Kotlin版本：
fun mergeSort(a: IntArray) {
val tmp = IntArray(a.size)
mergeSort(a, tmp, 0, a.size - 1)
}
fun mergeSort(a: IntArray, tmpArray: IntArray, left: Int, right: Int) {
if (left < right) {
val center = (left + right) / 2
mergeSort(a, tmpArray, left, center)
mergeSort(a, tmpArray, center + 1, right)
merge(a, tmpArray, left, center + 1, right)
}
}
fun merge(a: IntArray, tmpArray: IntArray, leftPos: Int, rightPos: Int, rightEnd: Int) {
var leftPos = leftPos
var rightPos = rightPos
var rightEnd = rightEnd
val leftEnd = rightPos - 1
var tmpPos = leftPos
val num = rightEnd - leftPos + 1
while (leftPos <= leftEnd && rightPos <= rightEnd) {
if (a[leftPos] < a[rightPos]) {
tmpArray[tmpPos++] = a[leftPos++]
} else {
tmpArray[tmpPos++] = a[rightPos++]
}
}
//左边还有剩余，copy
while (leftPos <= leftEnd) {
tmpArray[tmpPos++] = a[leftPos++]
}
//右边还有剩余，copy
while (rightPos <= rightEnd) {
tmpArray[tmpPos++] = a[rightPos++]
}
//将tmpArray copy back
var i = 0
while (i < num) {
a[rightEnd] = tmpArray[rightEnd]
i++
rightEnd--
}
}
(8)二分查找算法
也称为折半查找算法。Java版本：
/**
* 二分查找，基于已排序的数组，返回下标
*/
public static <T extends Comparable<? super T>> int binarySearch(T[] a, T x) {
int index = -1;
int low, high;
low = 0;
high = a.length - 1;
int middle;
while (low <= high) {
middle = (low + high) / 2;
if (x.compareTo(a[middle]) == 0) {
return middle;
} else if (x.compareTo(a[middle]) > 0) {
low = middle + 1;
} else {
high = middle - 1;
}
}
return index;
}
Kotlin版本：
/**
* 二分查找，基于已排序的数组，返回下标
*/
fun <T : Comparable<T>?> binarySearch(a: Array<T>, x: T): Int {
val index = -1
var low: Int
var high: Int
low = 0
high = a.size - 1
var middle: Int
while (low <= high) {
middle = (low + high) / 2
if (x!!.compareTo(a[middle]) == 0) {
return middle
} else if (x.compareTo(a[middle]) > 0) {
low = middle + 1
} else {
high = middle - 1
}
}
return index
}
还可以采用递归的方式，Java版本：
/**
* 二分查找 ，递归版本
*/
public static <T extends Comparable<? super T>> int binarySearch2(T[] a, T x) {
return binSearchRec(a, x, 0, a.length - 1);
}
private static <T extends Comparable<? super T>> int binSearchRec(T[] a, T x, int start, int end) {
int result = -1;
if (start <= end) {
int middle = (start + end) / 2;
if (a[middle].compareTo(x) > 0) {
return binSearchRec(a, x, start, middle - 1);
} else if (a[middle].compareTo(x) < 0) {
return binSearchRec(a, x, middle + 1, end);
} else {
return middle;
}
}
return result;
}
}
Kotlin版本：
/**
* 二分查找 ，递归版本
*/
fun <T : Comparable<T>?> binarySearch2(a: Array<T>, x: T): Int {
return binSearchRec(a, x, 0, a.size - 1)
}
private fun <T : Comparable<T>?> binSearchRec(a: Array<T>, x: T, start: Int, end: Int): Int {
val result = -1
if (start <= end) {
val middle = (start + end) / 2
return if (a[middle]!!.compareTo(x) > 0) {
binSearchRec(a, x, start, middle - 1)
} else if (a[middle]!!.compareTo(x) < 0) {
binSearchRec(a, x, middle + 1, end)
} else {
middle
}
}
return result
}
Over !
