閱讀目錄
- 分類及比較
- 冒泡排序
- 快速排序
- 選擇排序
- 插入排序
- 希爾排序
- 歸并排序
- 堆排序
1.分類及比較
排序 比較.jpg
2.冒泡排序
基本思想：兩個數(shù)比較大小，較大的數(shù)下沉挑豌，較小的數(shù)冒起來奈搜。
過程:
- 比較相鄰的兩個數(shù)據(jù)，如果第二個數(shù)小鄙麦，就交換位置典唇。
- 從后向前兩兩比較邮弹，一直到比較最前兩個數(shù)據(jù)。最終最小數(shù)被交換到起始的位置蚓聘，這樣第一個最小數(shù)的位置就排好了腌乡。
- 繼續(xù)重復(fù)上述過程，依次將第2.3...n-1個最小數(shù)排好位置夜牡。
代碼:
void BubbleSort(int *pData,int Count)
{
int iTemp;
for(int i=0;i<Count-1;i++)
{
for(int j=Count-1;j>i;j--)
{
if(pData[j]<pData[j-1])
{
iTemp=pData[j-1];
pData[j-1]=pData[j];
pData[j]=iTemp;
}
}
}
}
優(yōu)化: 略
3.快速排序
基本思想:
- 先從數(shù)列中取出一個數(shù)作為key值与纽；
- 將比這個數(shù)小的數(shù)全部放在它的左邊，大于或等于它的數(shù)全部放在它的右邊塘装；
- 對左右兩個小數(shù)列重復(fù)第二步急迂，直至各區(qū)間只有1個數(shù)。
代碼:
public static int[] qsort(int arr[],int start,int end) {
int pivot = arr[start];
int i = start;
int j = end;
while (i<j) {
while ((i<j)&&(arr[j]>pivot)) {
j--;
}
while ((i<j)&&(arr[i]<pivot)) {
i++;
}
if ((arr[i]==arr[j])&&(i<j)) {
i++;
} else {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
if (i-1>start) arr=qsort(arr,start,i-1);
if (j+1<end) arr=qsort(arr,j+1,end);
return (arr);
}
public static void main(String[] args) {
int arr[] = new int[]{3,3,3,7,9,122344,4656,34,34,4656,5,6,7,8,9,343,57765,23,12321};
int len = arr.length-1;
arr=qsort(arr,0,len);
for (int i:arr) {
System.out.print(i+"\t");
}
}
4.選擇排序
基本思想:
在長度為N的無序數(shù)組中蹦肴，第一次遍歷n-1個數(shù)僚碎，找到最小的數(shù)值與第一個元素交換；
第二次遍歷n-2個數(shù)阴幌，找到最小的數(shù)值與第二個元素交換勺阐；
。矛双。渊抽。
第n-1次遍歷，找到最小的數(shù)值與第n-1個元素交換议忽，排序完成懒闷。
代碼:
void SelectSort(int *a, int len){
int tmp;
for(int i=0; i<len-1; i++){
int k=i;
for(int j=i+1; j<len; j++){
if(a[j]<a[k])
k=j;
}
if(k!=i){
tmp=a[i];
a[i]=a[k];
a[k]=tmp;
}
}
}
5.插入排序
基本思想:
在要排序的一組數(shù)中，假定前n-1個數(shù)已經(jīng)排好序栈幸，現(xiàn)在將第n個數(shù)插到前面的有序數(shù)列中愤估，使得這n個數(shù)也是排好順序的。如此反復(fù)循環(huán)速址，直到全部排好順序玩焰。
代碼:
void InsertSort(int a[], int n)
{
for(int i= 1; i<n; i++){
if(a[i] < a[i-1]){ //若第i個元素大于i-1元素，直接插入壳繁。小于的話震捣，移動有序表后插入
int j= i-1;
int x = a[i]; //復(fù)制為哨兵，即存儲待排序元素
a[i] = a[i-1]; //先后移一個元素
while(x < a[j]){ //查找在有序表的插入位置
a[j+1] = a[j];
j--; //元素后移
}
a[j+1] = x; //插入到正確位置
}
}
}
6.希爾排序
基本思想:
在要排序的一組數(shù)中闹炉，假定前n-1個數(shù)已經(jīng)排好序蒿赢，現(xiàn)在將第n個數(shù)插到前面的有序數(shù)列中，使得這n個數(shù)也是排好順序的渣触。如此反復(fù)循環(huán)羡棵，直到全部排好順序。
代碼:
/**
* 直接插入排序的一般形式
*
* @param int dk 縮小增量嗅钻，如果是直接插入排序皂冰，dk=1
*
*/
void ShellInsertSort(int a[], int n, int dk)
{
for(int i= dk; i<n; ++i){
if(a[i] < a[i-dk]){ //若第i個元素大于i-1元素店展，直接插入。小于的話秃流，移動有序表后插入
int j = i-dk;
int x = a[i]; //復(fù)制為哨兵赂蕴，即存儲待排序元素
a[i] = a[i-dk]; //首先后移一個元素
while(x < a[j]){ //查找在有序表的插入位置
a[j+dk] = a[j];
j -= dk; //元素后移
}
a[j+dk] = x; //插入到正確位置
}
print(a, n,i );
}
}
/**
* 先按增量d（n/2,n為要排序數(shù)的個數(shù)進(jìn)行希爾排序
*
*/
void shellSort(int a[], int n){
int dk = n/2;
while( dk >= 1 ){
ShellInsertSort(a, n, dk);
dk = dk/2;
}
}
7.歸并排序
基本思想:
歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法的一個非常典型的應(yīng)用舶胀。
首先考慮下如何將2個有序數(shù)列合并概说。這個非常簡單，只要從比較2個數(shù)列的第一個數(shù)嚣伐，誰小就先取誰糖赔，取了后就在對應(yīng)數(shù)列中刪除這個數(shù)。然后再進(jìn)行比較轩端，如果有數(shù)列為空放典，那直接將另一個數(shù)列的數(shù)據(jù)依次取出即可。
略
8. 堆排序
略
