本文介绍一些经典的排序、查找算法。
(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 !
网友评论