1.冒泡排序：（稳定）O(n*n)
①.比较相邻的元素，如果前一个比后一个大，就把她们两个调换位置
①.对每一对相邻的元素作同样处理，从开始到最后一对，这步做完后，最后的元素会是最大的数。
//冒泡排序
//从小到大排序，从第一个元素开始，相邻元素比较，j比j+1大的，交换位置。
public class BubbleSort {
public static void swap(int a[],int i,int j){
int temp=0;
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
public static void bubbleSort(int a[]){
for(int i=0;i<a.length;i++){
for(int j=0;j<a.length-i-1;j++){
if(a[j]>a[j+1]){
swap(a,j,j+1);
}
}
}
}
public static void main(String[] args) {
int a[]={2,4,6,3,8,4,7,9,4};
bubbleSort(a);
for(int i=0;i<a.length;i++){
System.out.print(a[i]);
}
}
}
2.简单选择排序： <不稳定> O(n*n)
初始时在序列中找到最小（大）元素，放到序列的起始位置作为已排序序列；然后，再从剩余未排序元素中继续寻找最小（大）元素，放到已排序列的末尾。
//简单选择类排序，把第i个当成最小的，便利第i+1之后的，找到最小的和i交换。
public class SelectSort {
public static void swap(int a[],int i,int j){
int temp=0;
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
public static void selectSort(int a[]){
for(int i=0;i<a.length;i++){
int min=i;
for(int j=i+1;j<a.length;j++){
if(a[j]<a[min]){
min=j;
}
if(min!=i){
swap(a,min,i);
}
}
}
}
public static void main(String[] args) {
int a[]={2,5,3,6,4,7,5};
selectSort(a);
for(int i=0;i<a.length;i++){
System.out.print(a[i]);
}
}
}
3.直接插入排序 <稳定> 0(n*n)
/*思想：1.从第一个元素开始，该元素可以认为已经被排序。
* 2.取出下一个元素，在已经排序的元素序列中从后向前扫描
* 3.如果该元素（已排序）大于新元素，将该元素移到下一个位置。
* 4.重复3，直到找到已排序的元素小于或者等于新元素的位置。
* 5.将新元素插入到该位置。
/
public class InsertSort {
public static void insertSort(int a[]){
for(int i=1;i<a.length;i++){
int get=a[i];
/*int j=0;
for(j=i-1;j>=0&&get<a[j];j--){
a[j+1]=a[j];
}
a[j+1]=get;*/
int j=i-1;
while(j>=0&&a[j]>get){
a[j+1]=a[j];
j--;
}
a[j+1]=get;
}
}
public static void main(String[] args) {
int a[]={4,2,9,5,3};
insertSort(a);
for(int i=0;i<a.length;i++){
System.out.print(a[i]);
}
}
}
4.快速排序 <不稳定>
①.从序列中挑出一个元素，作为“基准”
②.把所有比基准值小的元素放在基准前面，把所有比基准值大的元素放在基准的后面
public class QuickSort {
public static void swap(int a[],int i,int j){
int temp=0;
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
public static int qSort(int a[],int low,int high){
int key;
key=a[low];
while(low<high){
while(low<high&&a[high]>=key)
high--;
swap(a,low,high);
while(low<high&&a[low]<=key)
low++;
swap(a,low,high);
}
return low;//此时 low和high在一个位置上。
}
public static void qSort2(int a[],int low,int high){
int pivot;
if(low<high){
pivot=qSort(a,low,high);
qSort2(a,low,pivot-1);
qSort2(a,pivot+1,high);
}
}
public static void main(String[] args) {
int a[]={2,5,3,6,4,7,5};
qSort2(a,0,a.length-1);
for(int i=0;i<a.length;i++){
System.out.print(a[i]);
}
}
}
