排序
849589-20190306165258970-1789860540.png
849589-20180402133438219-1946132192.png
1. 冒泡排序
相鄰的元素 比較和交換把曉得數(shù)字交換到最前面
例如：對(duì)5,3,8,6,4這個(gè)無序序列進(jìn)行冒泡排序。首先從后向前冒泡，4和6比較，把4交換到前面，序列變成5,3,8,4,6。同理4和8交換，變成5,3,4,8,6,3和4無需交換。5和3交換，變成3,5,4,8,6這樣一次冒泡就完了，把最小的數(shù)3排到最前面了。對(duì)剩下的序列依次冒泡就會(huì)得到一個(gè)有序序列。冒泡排序的時(shí)間復(fù)雜度為O(n^2)。
image.png
code:
public static int[] doIt(int[] arr){
int len = arr.length;
int temp;
for (int i = 0; i < len-1; i++) {
for (int j = 0;j<len-i-1;j++){
if (arr[j]>arr[j+1]){
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
return arr;
}
2. 選擇排序
從第一個(gè)位置開始選擇，選中第一個(gè)位置，依次對(duì)比，將最小的數(shù)字挪到這個(gè)位置。第二次選擇從第二個(gè)位置開始選，重復(fù)操作
選擇排序的時(shí)間復(fù)雜度為O(n^2)
image.png
code:
public static int[] doIt(int[] arr){
int len = arr.length;
int min;
int temp;
for (int i = 0; i < len-1; i++) {
min = i;
for (int j = i+1; j < len; j++){
if (arr[j]<arr[min]){
min = j;
}
}
if (min!=i){
temp = arr[min];
arr[min] = arr[i];
arr[i] = temp;
}
}
return arr;
}
3. 插入排序
- 默認(rèn)第一個(gè)為正確的排序
- 從第二個(gè)開始操作
- 第二個(gè)往前對(duì)比，如果比前一個(gè)小那么就將前一個(gè)往后移動(dòng)一位
- 第三也是重復(fù)操作
簡單插入排序的時(shí)間復(fù)雜度也是O(n^2)
image.png
code:
public static int[] doIt(int[] arr){
int len = arr.length;
int temp;
int j;
for (int i = 1; i < len; i++) {
j = i;
temp = arr[i];
while (j>0&&arr[j-1]>temp){
arr[j] = arr[j-1];
j--;
}
arr[j] = temp;
}
return arr;
}
4. 快速排序
image.png
code:
public static void quickSort(int[] arr,int low,int hight){
int i = low;
int j = hight;
if (low>=hight){
return;
}
int mid = arr[low];
while (low<hight){
while (low<hight && arr[hight] >= mid){
hight--;
}
if (low<hight){
arr[low] = arr[hight];
low++;
}
while (low<hight && arr[low] < mid){
low++;
}
if (low<hight){
arr[hight] = arr[low];
hight--;
}
}
arr[low] = mid;
//做前面的
quickSort(arr, i,low-1);
//做后面的
quickSort(arr,low+1,j);
}
public static int[] doIt(int[] arr){
int len = arr.length-1;
quickSort(arr,0, len);
return arr;
}
5. 堆排序
堆的性質(zhì)：所有的節(jié)點(diǎn)都不大于它的子節(jié)點(diǎn)。
組成堆可以從最后一個(gè)非葉子節(jié)點(diǎn)開始。
輸出:輸出堆頂，然后將最后一個(gè)元素提拔上來，進(jìn)行落底操作
code:
public class HeapSort {
public static void main(String[] args){
Arr arr = new Arr();
System.out.println("堆排序前"+arr.toString());
doIt(arr.getArr());
}
public static void heapOne(int[] arr, int length, int k){
int k1 = 2*k+1;
int k2 = 2*k+2;
//是否為葉子
if (k1>=length && k2>=length){
return;
}
int a1 = Integer.MAX_VALUE;
int a2 = Integer.MAX_VALUE;
//左孩子
if (k1<length){
a1 = arr[k1];
}
//右孩子
if (k2<length){
a2 = arr[k2];
}
//符合要求了
if(arr[k]<=a1 && arr[k]<=a2){
return;
}
if (a1<a2){
int t = arr[k];
arr[k] = arr[k1];
arr[k1] = t;
heapOne(arr, length, k1);
}else{
int t = arr[k];
arr[k] = arr[k2];
arr[k2] = t;
heapOne(arr, length, k2);
}
}
public static void doIt(int[] arr){
for (int i = arr.length - 1 / 2; i >= 0; i--) {
heapOne(arr,arr.length,i);
}
int len = arr.length;
while (len>0){
System.out.print(arr[0]+" ");
arr[0] = arr[len-1];
len--;
heapOne(arr,len, 0);
}
}
}
6. 希爾排序
7. 歸并排序
image
code:
public class MergeSort {
public static void main(String[] args) {
Arr arr = new Arr();
System.out.println("歸并排序前" + arr.toString());
doIt(arr.getArr(), 0, arr.getArr().length - 1);
System.out.println("歸并排序后" + arr.toString());
}
public static void doIt(int[] arr, int low, int high) {
int mid = (low + high) / 2;
if (low < high) {
doIt(arr, low, mid);
doIt(arr, mid + 1, high);
merge(arr, low, mid, high);
}
}
private static void merge(int[] arr, int low, int mid, int high) {
int[] temp = new int[high - low + 1];
int ai = low;
int bi = mid + 1;
int xi = 0;
while (ai <= mid && bi <= high) {
if (arr[ai] < arr[bi]) {
temp[xi++] = arr[ai++];
} else {
temp[xi++] = arr[bi++];
}
}
while (ai <= mid) {
temp[xi++] = arr[ai++];
}
while (bi <= high) {
temp[xi++] = arr[bi++];
}
for (int i=0;i<temp.length;i++){
arr[low+i] = temp[i];
}
}
}
