排序算法
1.冒泡排序（思路）
從前向后，即從下標(biāo)小的開始便锨，依次比較相鄰的兩個(gè)值怜奖，發(fā)現(xiàn)逆序（前面的大于后面的）則交換峦剔，最后大的值像氣泡一樣逐漸上冒
#需要設(shè)置標(biāo)識(shí)變量flag記錄交換次數(shù)
#核心還是交換，需要遍歷加判斷
#對(duì)數(shù)組進(jìn)行操作比較適合
#a【i】與a【i+1】
#每一次判讀一次惠勒，最多交換一次,交換后才算一趟
#錯(cuò)誤的赚抡，只有一趟
for（int i=0；i<size-1;i++){
if(a[i]>a[i+1]){
int t纠屋；
t=a[i];
a[i]=a[i+1];
a[i+1]=t;
}
}
#一個(gè)最大的數(shù)要比較好多次涂臣，一趟比較的次數(shù)，與交換的次數(shù)
#數(shù)組一共進(jìn)行n-1次的循環(huán)
#每一趟排序的次數(shù)在逐漸的減小
#第一趟排序，將最大的數(shù)排在最后
for（int i=0赁遗；i<size-1;i++){
if(a[i]>a[i+1]){
int t署辉；
t=a[i];
a[i]=a[i+1];
a[i+1]=t;
}
}
#第二趟排序，把第二大的數(shù)排在倒數(shù)第二位
for（int i=0岩四；i<size-1-1;i++){
if(a[i]>a[i+1]){
int t哭尝；
t=a[i];
a[i]=a[i+1];
a[i+1]=t;
}
}
.。剖煌。材鹦。。耕姊。桶唐。
#總的，需要多少趟箩做，size-1
for（int j=1莽红；j<size;j++){
? ??for（int i=0；i<size-1*j;i++){
? ??????if(a[i]>a[i+1]){
? ??????int t邦邦；
? ??????t=a[i];
? ??????a[i]=a[i+1];
? ??????a[i+1]=t;
}
}
}
#外面循環(huán)控制趟數(shù)
#里面循環(huán)控制每一趟交換的次數(shù)
#時(shí)間復(fù)雜度O（n^2）
#冒泡排序的優(yōu)化
如果某一趟發(fā)現(xiàn)沒有發(fā)生交換,則說明排序完成安吁。
boolean flag=flase；
for（int j=1燃辖；j<size;j++){
for（int i=0鬼店；i<size-j;i++){
if(a[i]>a[i+1]){
flag=true;
int t；
t=a[i];
a[i]=a[i+1];
a[i+1]=t;
}
}
if(!flag){
break;}
else{
flag=flase;}
}
#可以改變排序的趟數(shù)
#可以封裝成一個(gè)方法
2黔龟、選擇排序
選擇最小值與前面第一個(gè)數(shù)進(jìn)行交換
#先找再換
for(int i=0;i<size-1;i++){
#如何找最小值,通過相鄰比較和交換,把最小值交換到最后
if（a[i]>a[i+1]){
int t;
t=a[i];
a[i]=a[i+1];
a[i+1]=t;
}
}
#找到之后怎么辦妇智，賦值給第一個(gè)
a[0]=a[size-1];
#上面是第一次選擇
#第二次選擇
for(int i=1;i<size-1;i++){
#如何找最小值,通過相鄰比較和交換,把最小值交換到最后
if（a[i]>a[i+1]){
int t;
t=a[i];
a[i]=a[i+1];
a[i+1]=t;
}
}
#找到之后怎么辦，賦值給第一個(gè)
a[1]=a[size-1];
#總的選擇,外邊控制選擇次數(shù)氏身，里面控制數(shù)組下標(biāo)的開始巍棱，最后的下標(biāo)不變
for（int i=0;i<size-1;i++){
for(int j=0+i;j<size-1;j++){
#如何找最小值,通過相鄰比較和交換,把最小值交換到最后
if（a[j]>a[j+1]){
int t;
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
}
#找到之后怎么辦，賦值給第一個(gè)
a[i]=a[size-1];
}
#和冒泡排序類似
#每一輪排序得出一個(gè)結(jié)果
#和冒泡比蛋欣，比較的次數(shù)少了航徙。
#分步進(jìn)行，逐步推導(dǎo)
#排序就是比較和交換
#選擇排序還可以利用下標(biāo)交換陷虎，也可以值交換
#數(shù)組長(zhǎng)度是80000就可以理解了
#不同電腦同樣的程序運(yùn)行的時(shí)間是不同的
3.插入排序
#收試卷排序
思想：把數(shù)組看成一個(gè)有序表和一個(gè)無序表到踏，
開始時(shí)有序表是第一個(gè)值，然后從無序表中從第一個(gè)數(shù)開始取尚猿，依次插入到有序表中窝稿，其中需要通過判斷，知道插入的位置
#減少無序表比較和交換凿掂，增加有序表比較和交換
#用數(shù)組實(shí)現(xiàn)插入比較困難
#6個(gè)數(shù)據(jù)插入5次
#如何把值插入伴榔，創(chuàng)建一個(gè)新的數(shù)組嗎
#用交換代替插入，再原數(shù)組上進(jìn)行操作
#有序數(shù)組里面也要進(jìn)行多次比較和交換
#先處理插入的處理，再在外層循環(huán)處寫出取數(shù)據(jù)的循環(huán)
#第一次
for（int i=1潮梯；i<2;i++){
if(a[0]>a[i]){
int t;
t=a[0];
a[0]=a[i];
a[i]=t;
}
int startindex=0+1;
}
#第二次
for（int i=2骗灶；i<3;i++){
if(a[1]>a[i]){
int t;
t=a[1];
a[1]=a[i];
a[i]=t;
}
int startindex=1+1;
}
#需要設(shè)置更多變量來讓思路更明確
int startindex=1；
#設(shè)置出有序列表與無序列表的分界線秉馏，代表無序列表的第一個(gè)
#開始索引的意思也是插入數(shù)據(jù)的索引
#再次嘗試耙旦，插入的交換是從右到左
#知識(shí)沒有盲區(qū)，數(shù)據(jù)結(jié)構(gòu)用對(duì)萝究，思想理解對(duì)免都，寫對(duì)只是時(shí)間問題
##第一次
int startindex=1；
#設(shè)置比較次數(shù)
for（int i=startindex-1帆竹；i>=0;i--){
if(a[i]>a[startindex]){
int t;#交換數(shù)據(jù)用的
t=a[i];
a[i]=a[startindex];
a[startindex]=t;
}
startindex++;
}
##第二次
int startindex=2绕娘；
#設(shè)置比較次數(shù)，i為有序列表的索引
#插入時(shí)只排一次序栽连，故一個(gè)循環(huán)就夠了
for（int i=startindex-1险领；i>=0;i--){
#設(shè)置一個(gè)變量復(fù)制startindex的值從而進(jìn)行參與變化
#k需要放在循環(huán)這里
int k=startindex;
if(a[i]>a[k]){
int t;#交換數(shù)據(jù)用的
t=a[i];
a[i]=a[k];
#數(shù)據(jù)交換索引沒有交換
a[k]=t;
k--;
}
#插入之后，startindex才開始加一
}
startindex++;
###總的
需要加外層循環(huán)改變startindex的值
for(int startindex=1;startindex<size;startindex++){
#設(shè)置比較次數(shù)秒紧，i為有序列表的索引
#插入時(shí)只排一次序绢陌，故一個(gè)循環(huán)就夠了
for（int i=startindex-1；i>=0;i--){
#設(shè)置一個(gè)變量復(fù)制startindex的值從而進(jìn)行參與變化
#k需要放在循環(huán)這里
int k=startindex;
if(a[i]>a[k]){
int t;#交換數(shù)據(jù)用的
t=a[i];
a[i]=a[k];
#數(shù)據(jù)交換索引沒有交換
a[k]=t;
k--;
}
#插入之后熔恢，startindex才開始加一
}
}
#與選擇排序類似脐湾，進(jìn)階，減少了冒泡排序的比較次數(shù)
#需要引入變量k
#用for+while也行
#即大數(shù)后移
#小的數(shù)如果在后面會(huì)移動(dòng)次數(shù)過多
4.希爾排序
#先把數(shù)據(jù)存到數(shù)組中
#減少交換次數(shù)
思想：先把數(shù)組分組
同組的人隔著相同的增量
第一次分size/2=n組叙淌，第二次分n/2組秤掌，直到1組
分組后進(jìn)行插入排序
#如何對(duì)數(shù)組進(jìn)行分組i ，i+k
for（int i=0;i<size/2;i++){
if(a[i]>a[size/2+i]{
int t鹰霍；
t=a[i];
a[i]=a[size/2+i];
a[size/2+i]=t;
}
}
#如何分到最后剩兩組,怎么對(duì)數(shù)取整
if（size/2^n==1)
外層需要加一個(gè)n變換的循環(huán)
for(int n=1;n<log,n++){
}
#增量隨n變換
#但如果每組里面多個(gè)數(shù)據(jù)怎么辦,如何設(shè)置循環(huán)變量
for（int i=0;i<size/2^n;i++){
if(a[i]>a[size/2^n+i]{
int t闻鉴；
t=a[i];
a[i]=a[size/2+i];
a[size/2+i]=t;
}
}
#插入時(shí)采用交換法，或采用移動(dòng)法
#希爾排序快
#里面控制交換茂洒，外面控制步長(zhǎng)
5.快速排序
對(duì)冒泡算法的改進(jìn)
思想：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分成獨(dú)立的兩部分孟岛，
其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小
#需要找一個(gè)中間比較值
#時(shí)間復(fù)雜度一樣，所用的時(shí)間也不一定一樣
#遞歸
6.歸并排序
7.基數(shù)排序
######################################################
c語言有內(nèi)置的排序函數(shù)qsort（）
排序大多是針對(duì)數(shù)組的操作获黔，隊(duì)列，棧排序沒必要在验，樹玷氏，圖沒法排
鏈表可以排序
