时间复杂度
基本算法
1、选择排序
原理是对数组进行a进行遍历，假定a[i]是最小的，然后在与i之后的元素进行对比，如果找到比a[i]更小的，则进行位置替换。
public class SelertSort {
public void selectSort(int[] array) {
int min;
int tmp = 0;
for (int i = 0; i < array.length; i++) {
min = array[i];
for (int j = i; j < array.length; j++) {
if (array[j] < min) {
min = array[j];//最小值
tmp = array[i];
array[i] = min;
array[j] = tmp;
}
}
}
for(int num:array){
System.out.println(num);
}
}
public static void main(String [] args){
SelertSort selertSort = new SelertSort();
selertSort.selectSort(new int[]{9,4,2,6,7,3,10,33,88,1,17});
}
}
2、插入排序
下面是二分法插入，跟插入排序原理一样，不同的是在找插入元素的位置。普通的插入算法是一个当前节点进行数值比较的while循环，当遇到比插入的值大时就退出循环（从小到大排序）。之后将后面的元素进行后移，腾出位置放入要插入的元素。
2.1、二分法插入
public class BinaryInsertSort {
public static void main(String[] args) {
int[] a={49,38,65,97,176,213,227,49,78,34,12,164,11,18,1};
System.out.println("排序之前：");
for (int i = 0; i < a.length; i++) {
System.out.print(a[i]+" ");
}
//二分插入排序
sort(a);
System.out.println();
System.out.println("排序之后：");
for (int i = 0; i < a.length; i++) {
System.out.print(a[i]+" ");
}
}
//二分法插入
private static void sort(int[] a) {
for (int i = 0; i < a.length; i++) {
int temp = a[i];
int left = 0;
int right = i-1;
int mid = 0;
//确定要插入的位置
while(left<=right){
//先获取中间位置
mid = (left+right)/2;
if(temp<a[mid]){
//如果值比中间值小，让right左移到中间下标-1
right = mid-1;
}else{
//如果值比中间值大,让left右移到中间下标+1
left = mid+1;
}
}
for (int j = i-1; j >= left; j--) {
//以左下标为标准，在左位置前插入该数据，左及左后边全部后移
a[j+1] = a[j];
}
if(left != i){
//左位置插入该数据
a[left] = temp;
}
}
}
}
2.2、直接插入排序
public class InsertSort {
/**
* 直接插入排序
* @param args
*/
public static void main(String[] args) {
int[] a={49,38,65,97,76,13,27,49,78,34,12,64,1};
System.out.println("排序之前：");
for (int i = 0; i < a.length; i++) {
System.out.print(a[i]+" ");
}
//直接插入排序
for (int i = 1; i < a.length; i++) {
//待插入元素
int temp = a[i];
int j;
for (j = i-1; j>=0; j--) {
//将大于temp的往后移动一位
if(a[j]>temp){
a[j+1] = a[j];
}else{
break;
}
}
a[j+1] = temp;//插入进来
}
System.out.println();
System.out.println("排序之后：");
for (int i = 0; i < a.length; i++) {
System.out.print(a[i]+" ");
}
}
}
3、希尔排序
//不稳定
public class HeerSort {
//希尔排序
public static void main(String[] args) {
int[] a={49,38,65,97,76,13,27,49,78,34,12,64,1,33,85,29};
System.out.println("排序之前：");
for (int i = 0; i < a.length; i++) {
System.out.print(a[i]+" ");
}
//希尔排序
System.out.println();
int d = a.length/2;
while(true){
for(int i=0;i<d;i++){
for(int j=i;j+d<a.length;j+=d){
int temp;
if(a[j]>a[j+d]){
temp=a[j];
a[j]=a[j+d];
a[j+d]=temp;
}
}
}
if(d==1){break;}
d--;
}
System.out.println();
System.out.println("排序之后：");
for (int i = 0; i < a.length; i++) {
System.out.print(a[i]+" ");
}
}
}
