冒泡排序
~~~
import java.util.*;
public class BubbleSort {
public int[] bubbleSort(int[] A, int n) {
int temp = 0;
for(int i = 0; i < n - 1; i++){
for(int j = 0; j < n - i - 1; j++){
if(A[j] > A[j + 1]){
temp = A[j];
A[j] = A[j + 1];
A[j + 1] = temp;
}
}
}
return A;
}
}
~~~
选择排序
~~~
import java.util.*;
public class SelectionSort {
public int[] selectionSort(int[] A, int n) {
for(int i=0;i<n-1;i++)
for(int j=0;j<n-i-1;j++){
if(A[j]>A[j+1]){
int tmp=A[j];
A[j] = A[j+1];
A[j+1] =tmp;
}
}
return A;
}
}
~~~
插入排序
~~~
import java.util.*;
public class InsertionSort {
public int[] insertionSort(int[] A, int n) {
int i, j, temp;
for(i = 1; i < n; i++){
temp = A[i];
for(j = i; j > 0 && A[j - 1] > temp; j-- ){
A[j] = A[j - 1];
}
A[j] = temp;
}
return A;
}
}
~~~
归并排序
~~~
import java.util.*;
public class MergeSort {
public int[] mergeSort(int[] A, int n) {
if(A.length<2)
return A;
sort(A,0,n-1);
return A;
}
public void sort(int[] a,int s,int e){
if(s<e){
int m=(s+e)/2;
sort(a,s,m);
sort(a,m+1,e);
merge(a,s,m,e);
}
}
public void merge(int[] a,int s,int m,int e){
int len=e-s+1;
int[] arr=new int[len];
int p=s;
int q=m+1;
int t=0;
while(p<=m&&q<=e){
if(a[p]<a[q]){
arr[t++]=a[p++];
}else{
arr[t++]=a[q++];
}
}
while(p<=m){
arr[t++]=a[p++];
}
while(q<=e){
arr[t++]=a[q++];
}
int k=0;
for(int i=s;i<=e;++i){
a[i]=arr[k++];
}
}
}
~~~
快速排序
~~~
import java.util.*;
public class QuickSort {
public int[] quickSort(int[] A, int n) {
if(A.length<2)
return A;
sort(A,0,n-1);
return A;
}
public void sort(int[] arr, int left, int right) {
if (left < right) {
int random = left + (int) (Math.random() * (right - left + 1));
swap(arr, random, right);
int mid = partition(arr, left, right);
sort(arr, left, mid - 1);
sort(arr, mid + 1, right);
}
}
public int partition(int[] arr, int left, int right) {
int pivot = left - 1;
int index = left;
while (index <= right) {
if (arr[index] <= arr[right]) {
swap(arr, ++pivot, index);
}
index++;
}
return pivot;
}
public void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
~~~
堆排序
> 1.构造最大堆（Build_Max_Heap）：若数组下标范围为0~n，考虑到单独一个元素是大根堆，则从下标n/2开始的元素均为大根堆。于是只要从n/2-1开始，向前依次构造大根堆，这样就能保证，构造到某个节点时，它的左右子树都已经是大根堆。
> 2.堆排序（HeapSort）：由于堆是用数组模拟的。得到一个大根堆后，数组内部并不是有序的。因此需要将堆化数组有序化。思想是移除根节点，并做最大堆调整的递归运算。第一次将heap[0]与heap[n-1]交换，再对heap[0...n-2]做最大堆调整。第二次将heap[0]与heap[n-2]交换，再对heap[0...n-3]做最大堆调整。重复该操作直至heap[0]和heap[1]交换。由于每次都是将最大的数并入到后面的有序区间，故操作完后整个数组就是有序的了。
> 3.最大堆调整（Max_Heapify）：该方法是提供给上述两个过程调用的。目的是将堆的末端子节点作调整，使得子节点永远小于父节点 。
~~~
import java.util.*;
public class HeapSort {
public int[] heapSort(int[] A, int n) {
buildHeap(A, n);
for(int i = n - 1; i >= 0; i--){
int temp = A[0];
A[0] = A[i];
A[i] = temp;
heapAdjust(A, i, 0);
}
return A;
}
void buildHeap(int[] A, int n){
for(int i = n / 2; i >= 0; i--){
heapAdjust(A, n, i);
}
}
void heapAdjust(int[] A, int n, int cur){
int left = cur * 2 + 1;
int right = cur * 2 + 2;
int largest = cur;
if(left < n && A[left] > A[largest]){
largest = left;
}
if(right < n && A[right] > A[largest]){
largest = right;
}
if(largest != cur){
int temp = A[cur];
A[cur] = A[largest];
A[largest] = temp;
heapAdjust(A, n, largest);
}
}
}
~~~
希尔排序
~~~
import java.util.*;
public class ShellSort {
public int[] shellSort(int[] arr, int n) {
if (arr == null || arr.length < 2) {
return arr;
}
int feet = arr.length / 2;
int index = 0;
while (feet > 0) {
for (int i = feet; i < arr.length; i++) {
index = i;
while (index >= feet) {
if (arr[index - feet] > arr[index]) {
swap(arr, index - feet, index);
index -= feet;
} else {
break;
}
}
}
feet /= 2;
}
return arr;
}
public void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
~~~
计数排序
~~~
import java.util.*;
public class CountingSort {
public int[] countingSort(int[] A, int n) {
if(A.length<2)
return A;
int min=A[0];
int max=A[0];
for(int i=1;i<A.length;++i){
min=Math.min(min,A[i]);
max=Math.max(max,A[i]);
}
int[] countArr=new int[max-min+1];
for(int i=0;i<A.length;++i){
countArr[A[i]-min]++;
}
int p=0;
for(int i=0;i<countArr.length;++i){
while(countArr[i]>0){
A[p++]=i+min;
countArr[i]--;
}
}
return A;
}
}
~~~
基数排序
~~~
import java.util.*;
public class RadixSort {
int[] radixSort(int[] A, int n) {
ArrayList<LinkedList<Integer>> buket = new ArrayList<LinkedList<Integer>>();
for (int i = 0; i < 10; i++) {
buket.add(new LinkedList<Integer>());
}
//五位数
for (int k = 1; k <= 10000; k *= 10) {
for (int i = 0; i < n; i++) {
buket.get(A[i] / k % 10).offer(A[i]);
}
int index = 0;
for (int i = 0; i < 10; i++) {
while (!buket.get(i).isEmpty()) {
A[index++] = buket.get(i).removeFirst();
}
}
}
return A;
}
}
~~~
###小结：
计数排序与基数排序都是稳定的排序算法，平均时间复杂度为O(n)，空间复杂度O(m)
###练习：
> 1.已知一个几乎有序的数组，几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离可以不超过k，并且k相对于数组来说比较小。请选择一个合适的排序算法针对这个数据进行排序。
> 给定一个int数组A，同时给定A的大小n和题意中的k，请返回排序后的数组。
> 测试样例：
> [2,1,4,3,6,5,8,7,10,9],10,2
> 返回：[1,2,3,4,5,6,7,8,9,10]
参考答案：堆排序
* * * * *
> 2.请设计一个高效算法，判断数组中是否有重复值。必须保证额外空间复杂度为O(1)。
> 给定一个int数组A及它的大小n，请返回它是否有重复值。
> 测试样例：
> [1,2,3,4,5,5,6],7
> 返回：true
参考答案：堆排序
* * * * *
> 3.有两个从小到大排序以后的数组A和B，其中A的末端有足够的缓冲空容纳B。请编写一个方法，将B合并入A并排序。
> 给定两个有序int数组A和B，A中的缓冲空用0填充，同时给定A和B的真实大小int n和int m，请返回合并后的数组。
~~~
import java.util.*;
public class Merge {
public int[] mergeAB(int[] A, int[] B, int n, int m) {
int index=n+m-1;
int j=n-1;
int k=m-1;
while(j>=0&&k>=0){
if(A[j]>B[k]){
A[index--]=A[j--];
}else{
A[index--]=B[k--];
}
}
while(j>=0){
A[index--]=A[j--];
}
while(k>=0){
A[index--]=B[k--];
}
return A;
}
}
~~~
* * * * *
> 4.有一个只由0，1，2三种元素构成的整数数组，请使用交换、原地排序而不是使用计数进行排序。
给定一个只含0，1，2的整数数组A及它的大小，请返回排序后的数组。保证数组大小小于等于500。
测试样例：
[0,1,1,0,2,2],6
返回：[0,0,1,1,2,2]
~~~
import java.util.*;
public class ThreeColor {
public int[] sortThreeColor(int[] A, int n) {
if(A.length<2)
return A;
int p=-1;
int q=A.length;
int i=0;
while(i<q){
if(A[i]==0){
swap(A,i++,++p);//i自加腾位置
}else if(A[i]==2){
swap(A,i,--q);
}else{
i++;
}
}
return A;
}
public void swap(int[] a,int i,int j){
int t=a[i];a[i]=a[j];a[j]=t;
}
}
~~~
* * * * *
> 5.现在有一个行和列都排好序的矩阵，请设计一个高效算法，快速查找矩阵中是否含有值x。
给定一个int矩阵mat，同时给定矩阵大小nxm及待查找的数x，请返回一个bool值，代表矩阵中是否存在x。所有矩阵中数字及x均为int范围内整数。保证n和m均小于等于1000。
测试样例：
[[1,2,3],[4,5,6],[7,8,9]],3,3,10
返回：false
~~~
import java.util.*;
public class Finder {
public boolean findX(int[][] mat, int n, int m, int x) {
int row = 0,col = m-1;
while(row<n && col>=0){
if(mat[row][col] == x)
return true;
else if(mat[row][col] > x)
col--;
else
row++;
}
return false;
}
}
~~~
* * * * *
> 6.对于一个数组，请设计一个高效算法计算需要排序的最短子数组的长度。
给定一个int数组A和数组的大小n，请返回一个二元组，代表所求序列的长度。(原序列位置从0开始标号,若原序列有序，返回0)。保证A中元素均为正整数。
测试样例：
[1,4,6,5,9,10],6
返回：2
~~~
import java.util.*;
public class Subsequence {
public int shortestSubsequence(int[] A, int n) {
// write code here
if(A.length<2)
return 0;
int max = A[0],min = A[n-1],r = 0,l = 0;
for (int i = 0;i < n;i++) {
//A[i]比前面的数大就把大的数记录下来
if (A[i] > max) max = A[i];
//A[i]比前面的数小就只记录索引的位置
else if (A[i] < max) r = i;
}
for (int j = n-1;j >= 0;j--) {
if (A[j] < min) min = A[j];
else if (A[j] > min) l = j;
}
if (r-l == 0) return 0;
else return r-l+1;
}
}
~~~
