1 排序
排序基本信息
稳定性：排序前大的数在排序后，大的数依然保持不变就是稳定排序，反之不稳定
内外排序：根据待排序的记录是否放在内存里面区分的。诸如：插入排序（直接插入&希尔）、交换排序（冒泡&快排）、选择排序（简单选择&堆排）、归并排序（归并）。
算法性能影响：时间性能、辅助空间、算法复杂性（算法本身的复杂度跟时间复杂度区分开）。
简单算法：冒泡排序、简单选择排序、直接插入排序
改进算法：希尔排序（不稳定）、堆排序（不稳定）、归并排序、快排（不稳定）
总之：排序四大类，简单有三种，改进为四种。不稳多改进算法
排序方法 平均情况 最好情况 最坏情况 辅助空间 稳定性
冒泡排序 O(N^2) O(N) O(N^2) O(1) 稳定
简单选择 O(N^2) O(N^2) O(N^2) O(1) 稳定
直接插入 O(N^2) O(N) O(N^2) O(1) 稳定
希尔排序 O(NlogN~N^2)O(N^1.3) O(N^2) O(1) 不稳定
堆排序 O(NlogN) O(NlogN) O(NlogN) O(1) 不稳定
归并排序 O(NlogN) O(NlogN) O(NlogN) O(N) 稳定
快速排序 O(NlogN) O(NlogN) O(N^2) O(logN~N) 不稳定
简单算法：冒泡排序
个人名片：我是冒泡排序,稳定性较好，是内排序中的交换排序，也是简单排序会员。基本思想，哦也可以说个人介绍：两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。
Java实现：
import java.util.Queue;
import java.util.Stack;
public class BagDome {
/*交换数据函数*/
public static void swap(int[] arr,int i,int j){
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
public static void swap1(int[] arr,int i,int j){
arr[i]=arr[i]^arr[j];
arr[j]=arr[i]^arr[j];
arr[i]=arr[i]^arr[j];
}
/*遍历读取数组*/
public static void printarr(int[] arr){
for(int i:arr){
System.out.print(" "+i);
}
}
//1 对记录作交换排序（冒泡排序的初级版），例如int[] a={9,1,5,8,3,7,4,6,2};
public static void BubbleSort1(int[] arr){
for(int i=0;i<arr.length;i++){
for(int j=i+1;j<arr.length;j++){
if(arr[i]>arr[j]){
swap(arr,i,j);
}
}
}
}
//2 对记录进行冒泡排序（改进版）,例如int[] a={9,1,5,8,3,7,4,6,2};
public static void BubbleSort2(int[] arr){
for(int i=0;i<arr.length;i++){
for(int j=arr.length-2;j>=i;j--){
if(arr[j]>arr[j+1]){
swap(arr,j,j+1);
}
}
}
}
//3 基本有序的冒泡优化算法，例如int[] a={2,1,3,4,5,6,7,8,9};
public static void BubbleSort3(int[] arr){
boolean flag=true;
for(int i=0;i<arr.length && flag;i++){
for(int j=arr.length-2;j>=i;j--){
if(arr[j]>arr[j+1]){
swap(arr,j,j+1);
flag=false;
}
}
}
}
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
//int[] arr={9,1,5,8,3,7,4,6,2};
int[] arr={2,1,3,4,5,6,7,8,9};
System.out.print("冒泡排序前： ");
printarr(arr);
//BubbleSort1(arr);
//BubbleSort2(arr);
BubbleSort3(arr);
System.out.print("
冒泡排序后： ");
printarr(arr);
}
}
简单排序：简单选择排序
个人名片：我是简单选择排序,稳定性较好，是内排序中的选择排序，也是简单排序会员。基本思想：。