排序
package com.example.singleton;
import android.os.Bundle;
import android.support.v7.app.AppCompatActivity;
import android.view.View;
import java.util.Arrays;
public class MainActivity extends AppCompatActivity {
int[] arry = {29, 26, 88, 69};
@Override
protected void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
setContentView(R.layout.activity_main);
findViewById(R.id.tv_test).setOnClickListener(new View.OnClickListener() {
@Override
public void onClick(View v) {
bubbleSort(arry);
insertSort(arry);
choiceSort(arry);
}
});
}
/**
* 冒泡排序
* 基本思想 在要排序的一组数中 对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒
* 每当两个相邻的数比较后发现他们的排序与排序要求相反时 就将他们互换
*
* @author zanyang
* created at 2017/7/19 15:47
*/
public static int[] bubbleSort(int[] arry) {
for (int i = 0; i < arry.length; i++) {
for (int j = i; j < arry.length - i - 1; j++) {
if (arry[j] > arry[j + 1]) {
int temp = arry[j];
arry[j] = arry[j + 1];//交换顺序 大的在后小的在前
arry[j + 1] = temp;
}
}
}
DebugLog.e(">>>>>>>>>>>>>>>"+ Arrays.toString(arry));
return arry;
}
/**
* 插入排序
*
* @author zanyang
* created at 2017/7/19 17:43
*/
public static int[] insertSort(int[] arry) {
// TODO: 2017/7/19 从数组第二位开始，第一位为初始排好的顺序
for (int i = 1; i < arry.length; i++) {
int temp = arry[i];// TODO: 2017/7/19 保存待插入的数值
int j = i - 1;// TODO: 2017/7/19 当前数值的前一位数组角标
for (j = i - 1; j >= 0; j--) {
if (arry[j] > temp) {
arry[j + 1] = arry[j];// TODO: 2017/7/19 将前一位数值移动一位
} else {
break;
}
}
arry[j + 1] = temp;
}
DebugLog.e(">>>>>>>>>>>>>>>"+ Arrays.toString(arry));
return arry;
}
/**
* 选择排序
* 思想 在要排序的一组数中，选出最小的一个数与第一个位置的数交换
* 在剩下的数当中再找最小的与第二个位置的数交换 如此循环到 倒数第二个数和最后一个数比较为止
*
* @author zanyang
* created at 2017/7/19 18:07
*/
public static int[] choiceSort(int[] arry) {
for (int i = 0; i < arry.length; i++) {
int low = i;
for (int j = i + 1; j < arry.length; j++) {
if (arry[j] < arry[low]) {
low = j; // 当前最小值位置
}
}
int temp = arry[i];
arry[i] = arry[low];
arry[low] = temp;
}
DebugLog.e(">>>>>>>>>>>>>>>"+ Arrays.toString(arry));
return arry;
}
/**
* 快速排序
* 基本思想 选择一个基准元素 通常选择第一个元素或者hi最后一个元素 通过一趟扫描 将待排序列分成两个部分 一个部分比基准元素小 一部分大于等于基准元素 此时基准元素在其排好序后
* 的正确位置 然后再用相同的方法递归排序划分的两部分
*
* @author zanyang
* created at 2017/7/20 15:40
*/
public static int[] quickSort(int[] arry){
return arry;
}
}
复杂度 O() 读 欧恩
平均时间复杂度比较：
冒泡：O(n^2)
插入：O(n^2)
选择：O(n^2)
快排：O(nlgn)
稳定性：
冒泡：稳定
插入：稳定
选择：不稳定
快排：不稳定
