排序
849589-20190306165258970-1789860540.png
849589-20180402133438219-1946132192.png
1. 冒泡排序
相邻的元素 比较和交换把晓得数字交换到最前面
例如：对5,3,8,6,4这个无序序列进行冒泡排序。首先从后向前冒泡，4和6比较，把4交换到前面，序列变成5,3,8,4,6。同理4和8交换，变成5,3,4,8,6,3和4无需交换。5和3交换，变成3,5,4,8,6这样一次冒泡就完了，把最小的数3排到最前面了。对剩下的序列依次冒泡就会得到一个有序序列。冒泡排序的时间复杂度为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. 选择排序
从第一个位置开始选择，选中第一个位置，依次对比，将最小的数字挪到这个位置。第二次选择从第二个位置开始选，重复操作
选择排序的时间复杂度为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. 插入排序
- 默认第一个为正确的排序
- 从第二个开始操作
- 第二个往前对比，如果比前一个小那么就将前一个往后移动一位
- 第三也是重复操作
简单插入排序的时间复杂度也是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. 堆排序
堆的性质：所有的节点都不大于它的子节点。
组成堆可以从最后一个非叶子节点开始。
输出:输出堆顶，然后将最后一个元素提拔上来，进行落底操作
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];
}
}
}
