冒泡排序
~~~
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;
}
}
~~~
