一、排序算法
/**
* 给定数组：int data[] = {9,2,7,19,100,97,63,208,55,78}
* 一、直接插入排序(内部排序、O(n2)、稳定),
* 复杂度：最好 - 最坏 - 平均 O(n) - O(n^2) - O(n^2)
* 原理：从待排序的数中选出一个来，插入到前面的合适位置。
*/
public static void insertSort() {
int tmp, j = 0;
for (int k = 0; k < data.length; k++) {//-----1-----
tmp = data[k];//暂存
j = k - 1;
while (j >= 0 && tmp < data[j]) {//-----2-----
data[j + 1] = data[j];
j--;
}
data[j + 1] = tmp;//------3-------
}
}
/**
* 二、选择排序（O(n2)、不稳定）最好O(n^2) - 最坏O(n^2) - 平均O(n^2)
* 与直接插入排序正好相反，选择排序是从待排序的数中选出最小的放在已经排好的后面，这个算法选数耗时。
*/
public static void selectSort() {
int i, j, k, tmp = 0;
for (i = 0; i < data.length - 1; i++) {
k = i;
for (j = i + 1; j < data.length; j++)
if (data[j] < data[k])
k = j;
if (k != i) {
tmp = data[i];
data[i] = data[k];
data[k] = tmp;
}
}
}
/**
* 三、快速排序（O(nlogn)、不稳定），最好O(nlgn) - 最坏O(n^2) - 平均O(nlgn)
* 快速排序简称快排，是一种比较快的排序，适合基本无序的数据，
* 为什么这么说呢？下面我说下快排的思路：
* 设置两个指针：i和j，分别指向第一个和最后一个，i像后移动，j向前移动，
* 选第一个数为标准（一般这样做，当然快排的关键就是这个“标准”的选取），
* 从后面开始，找到第一个比标准小的数，互换位置，然后再从前面，
* 找到第一个比标准大的数，互换位置，第一趟的结果就是标准左边的都小于标准，
* 右边的都大于标准（但不一定有序），分成两拨后，继续递归的使用上述方法，最终有序！
*/
static class QuickSort {
public int data[];
private int partition(int array[], int low, int high) {
int key = array[low];
while (low < high) {
while (low < high && array[high] >= key)
high--;
array[low] = array[high];
while (low < high && array[low] <= key)
low++;
array[high] = array[low];
}
array[low] = key;
return low;
}
public int[] sort(int low, int high) {
if (low < high) {
int result = partition(data, low, high);
sort(low, result - 1);
sort(result + 1, high);
}
return data;
}
}
/**
* 四、冒泡排序（稳定、基本有序可达O(n)，最坏情况为O(n2)）
* 最好 - 最坏 - 平均 O(n) - O(n^2) - O(n^2)
* 冒泡排序是一种很简单，不论是理解还是时间起来都比较容易的一种排序算法，
* 思路简单：小的数一点一点向前起泡，最终有序。
* 相邻两个元素比较大小进行交换，一趟冒泡后会有一个元素到达最终位置
*/
public static void bubbleSort() {
int i, j, tmp = 0;
boolean flag;
for (i = 0; i < data.length - 1; i++) {
flag = false;
for (j = data.length - 1; j > i; j--) {
if (data[j] < data[j - 1]) {
tmp = data[j];
data[j] = data[j - 1];
data[j - 1] = tmp;
}
if (flag == false) {
return;
}
}
}
}
/**
* 五、希尔排序（不稳定）
* 最好O(n) - 最坏O(n^s 1<s<2) - 平均O(n^1.3)
* 按步长进行分组，组内直接插入，缩小增量再次进行此步骤，增量为1时相当于一次直接插入。
*/
public void shellSort(int[] a) {
if (null == a || a.length < 2) {
return;
}
for (int d = a.length/2; d > 0; d/=2) {
for (int i = d; i < a.length; i++) {
// 内部直接插入
int temp = a[i];
int j = i - d;
while (j >= 0 && temp < a[j]) {
a[j+d] = a[j];
j -= d;
}
a[j+d] = temp;
}
}
}
/**
* 六、归并排序（稳定）
* 最好O(nlgn) - 最坏O(nlgn) - 平均O(nlgn)
* 两个有序序列的合并，方法：分治 + 递归
*/
public void mergeSort(int[] a, int low, int high) {
int mid = (low + high) / 2;
if (low < high) {
//左边
mergeSort(a, low, mid);
//右边
mergeSort(a, mid + 1, high);
//有序序列归并
merge(a, low, mid, high);
}
}
private void merge(int[] a, int low, int mid, int high) {
int[] temp = new int[high - low + 1];
// 左指针
int i = low;
// 右指针
int j = mid + 1;
// 临时数组指针
int k = 0;
while (i <= mid && j <= high) {
if (a[i] < a[j]) {
temp[k++] = a[i++];
} else {
temp[k++] = a[j++];
}
}
//左边剩余
while (i <= mid) {
temp[k++] = a[i++];
}
//右边剩余
while (j <= high) {
temp[k++] = a[j++];
}
// 倒出
for (int t = 0; t < temp.length; t++) {
a[t + low] = temp[t];
}
}
/**
* 七、堆排序（稳定）
* O(nlogn) [平均 - 最好 - 最坏]
* 利用堆的特性
*/
public void heapSort(int[] a) {
if (null == a || a.length < 2) {
return;
}
buildMaxHeap(a);
for (int i = a.length - 1; i >= 0; i--) {
int temp = a[0];
a[0] = a[i];
a[i] = temp;
adjustHeap(a, i, 0);
}
}
// 建堆
private void buildMaxHeap(int[] a) {
for (int i = a.length/2; i >= 0; i--) {
adjustHeap(a, a.length, i);
}
}
// 调整堆
private void adjustHeap(int[] a, int size, int parent) {
int left = 2 * parent + 1;
int right = 2 * parent + 2;
int largest = parent;
if (left < size && a[left] > a[largest]) {
largest = left;
}
if (right < size && a[right] > a[largest]) {
largest = right;
}
if (parent != largest) {
int temp = a[parent];
a[parent] = a[largest];
a[largest] = temp;
adjustHeap(a, size, largest);
}
}
二、查找算法
/**
* 典型的二分查找
* 对于二分查找算法要求, 查找前的数据必须是已经排好序的,
* 然后得到数组的开始位置start和结束位置end,
* 取中间位置mid的数据a[mid]跟待查找数据key进行比较,
* 若 a[mid] > key, 则取end = mid - 1;
* 若 a[mid] < key, 则取start = mid + 1;
* 若 a[mid] = key 则直接返回当前mid为查找到的位置.
* 依次遍历直到找到数据或者最终没有该条数据.
*/
//已经排好序的数组
public static int binarySearch(int[] nums, int key) {
int start = 0;
int end = nums.length - 1;
int mid = -1;
while (start <= end) {
mid = (start + end) / 2;
if (nums[mid] == key) {
return mid;//已经查到返回！
} else if (nums[mid] > key) {
end = mid - 1;
} else if (nums[mid] < key) {
start = mid + 1;
}
}
return -1;
}
//排序算法
/**
* 务必注意: 以下所有的排序算法都是从1开始, 而不是从0开始, 有的排序算法会把0位置当作监视哨
* 排序之前先写一个交换方法后面会用到
*/
private static void swap(int[] a, int i, int j) {
a[i] ^= a[j];
a[j] ^= a[i];
a[i] ^= a[j];
}
//插入排序
/**
* 插入排序的基本思想是，经过i-1遍处理后,L[1..i-1]己排好序。
* 第i遍处理仅将L[i]插入L[1..i-1]的适当位置，使得L[1..i] 又是排好序的序列。
* 要达到这个目的，我们可以用顺序比较的方法。
* 首先比较L[i]和L[i-1]，如果L[i-1]≤ L[i]，则L[1..i]已排好序，第i遍处理就结束了；
* 否则交换L[i]与L[i-1]的位置，继续比较L[i-1]和L[i-2]，
* 直到找到某一个位置j(1≤j≤i-1)，使得L[j] ≤L[j+1]时为止。
* 图1演示了对4个元素进行插入排序的过程，共需要(a),(b),(c)三次插入
* 稳定，时间复杂度 O(n^2)
*/
public static void insertSort(int[] a) {//a0为监视哨位置,不作为数据存储
int len = a.length;
for (int i = 2; i < len; i++) {
if (a[i - 1] > a[i]) {
a[0] = a[i];
a[i] = a[i - 1];
int j = 0;
for (j = i - 2; a[j] > a[0]; j--) {
a[j + 1] = a[j];
}
a[j + 1] = a[0];
}
}
}
//选择排序
/**
* 选择排序的基本思想是对待排序的记录序列进行n-1遍的处理，
* 第i遍处理是将L[i..n]中最小者与L[i]交换位置。
* 这样，经过i遍处理之后，前i个记录的位置已经是正确的了。
* 不稳定, 时间复杂度 O(n^2)
*/
public static void selectSort(int[] a) {
for (int i = 1; i < a.length; i++) {
int j = selectMinKey(a, i); //从i开始a.length中找到最小的位置
if (i != j) {
swap(a, i, j);
}
}
}
// 查找从i开始到a.length中最小的位置
private static int selectMinKey(int[] a, int i) {
int key = i;
for (int j = i + 1; j < a.length; j++) {
if (a[j] < a[key]) {
key = j;
}
}
return key;
}
//冒泡排序
/**
* 冒泡排序方法是最简单的排序方法。
* 这种方法的基本思想是，将待排序的元素看作是竖着排列的“气泡”，较小的元素比较轻，从而要往上浮。
* 在冒泡排序算法中我们要对这个“气泡”序列处理若干遍。
* 所谓一遍处理，就是自底向上检查一遍这个序列，并时刻注意两个相邻的元素的顺序是否正确。
* 如果发现两个相邻元素的顺序不对，即“轻”的元素在下面，就交换它们的位置。
* 显然，处理一遍之后，“最轻”的元素就浮到了最高位置；处理二遍之后，“次轻”的元素就浮到了次高位置。
* 在作第二遍处理时，由于最高位置上的元素已是“最轻”元素，所以不必检查。
* 一般地，第i遍处理时，不必检查第i高位置以上的元素，因为经过前面i-1遍的处理，它们已正确地排好序。
* 稳定，时间复杂度 O(n^2)
*/
//冒泡排序
public static void bubbleSort(int[] a) {
int len = a.length;
for (int i = 1; i < len - 1; i++) {
for (int j = i; j < len - i; j++) {
if (a[j + 1] < a[j]) {
swap(a, j + 1, j);
}
}
}
}
//快速排序
/**
* 不稳定，时间复杂度 最理想 O(nlogn) 最差时间O(n^2)
* <p>
* 快速排序是对冒泡排序的一种本质改进。
* 它的基本思想是通过一趟扫描后，使得排序序列的长度能大幅度地减少。
* 在冒泡排序中，一次扫描只能确保最大数值的数移到正确位置，而待排序序列的长度可能只减少1。
* 快速排序通过一趟扫描，就能确保某个数（以它为基准点吧）的左边各数都比它小，右边各数都比它大。
* 然后又用同样的方法处理它左右两边的数，直到基准点的左右只有一个元素为止。
*/
//快速排序
public static void quickSort(int[] a, int low, int high) {
//递归快速排序
int pivotLoc = 0;//中心点
if (low < high) {
pivotLoc = partitionLoc(a, low, high);
quickSort(a, low, pivotLoc - 1);
quickSort(a, pivotLoc + 1, high);
}
}
//获取到a的下标 low ~ high 中, a[low]的应该放的位置, 即左边的数 < a[low] 右边的数 > a[low]
private static int partitionLoc(int[] a, int low, int high) {
a[0] = a[low];
while (low < high) {
while (low < high && a[high] >= a[0]) {
high--;
}
a[low] = a[high];
while (low < high && a[low] <= a[0]) {
low++;
}
a[high] = a[low];
}
a[low] = a[0];
return low;
}
网友评论