5種排序
- 1冒泡排序
- 偽代碼
- 原理
- 代碼實作
- 2插入排序
- 偽代碼
- 原理
- 代碼實作
- 3時間復雜度下屆
- 4希爾排序
- 偽代碼
- 代碼實作
- Hibbard序列
- 5選擇排序
- 選擇排序原理
- 偽代碼
- 代碼實作
- 6堆排序
- 堆排序基礎程式(堆的建立,插入,洗掉)
- 堆排序演算法1(核心程式)
- 堆排序演算法1代碼實體
- 7有序子列的歸并
- 歸并演算法代碼實作
1冒泡排序
1.待排序資料在陣列和鏈表均可
2.當嚴格不等的時候,才交換,就是說當等于的時候,不交換這說明演算法是穩定的
偽代碼
void Bubble_Sort(ElementType A[], int N)
{
for (p = N - 1; p > 0; p--)
{
flag = 0;
for (i = 0; i < p; i++)
{
if (A[i] > A[i-1])
{
swap(A[i] , A[i-1]);
flag = 1;
}
}
if (flag == 0)
break;
}
}
原理
第一個數與第二個數比較,如果第一個大,那么互換位置,然后第二個第三個比較,以此類推,第一輪過后,最大值放在了最后
代碼實作
#include<stdio.h>
int main()
{
int i,*pointer;
void swap(int *m, int *n);
void pailie(int A[], int N);
int arr[8] = { 2,1,6,7,8,9,1,1 };
pailie(arr,8);
for (i = 0; i < 8; i++)
{
printf("%d", arr[i]);
}
return 0;
}
void pailie(int *p_1, int N)
{
int flag;
int i,p;
void swap(int m, int n);
for (p = N - 1; p > 0; p--)
{
flag = 0;
for (i = 0; i < p; i++)
{
if (*(p_1+i) > *(p_1+i+1))
{
swap(p_1 + i, p_1 + i + 1);
flag = 1;
}
}
if (flag == 0)
break;
}
}
void swap(int *m, int *n)
{
int temp;
temp = *m;
*m = *n;
*n = temp;
}
11126789
復雜度O(n),O(n平方)
2插入排序
偽代碼
void Insertion_Sort(ElementType A[], int N)
{
for (p = 1; p < N; p++)
{
tmp =A[p];
for (i = p; i > 0 && A[i-1] > tmp; i--)
A[i]=A[i-1];
A[i] = tmp;
}
}
原理
比如我現在在打牌,每次拿到一張牌,就要把牌從小到大排列;我現在有3張牌,分別是2,6,4;已經把這三張按照順序排好了,然后我又拿了一張5,從右開始比較發現6大于5,就把6放在第四張,然后與第二張4比較,5大于4,所以新牌5就落位,
代碼實作
#include<stdio.h>
int main()
{
void paicu_2(int* pointer, int N);
int i;
int arr[8] = { 1,9,5,4,5,6,7,9 };
paicu_2(arr, 8);
for (i = 0; i < 8; i++)
{
printf("%d", arr[i]);
}
return 0;
}
void paicu_2(int *pointer, int N)
{
int tmp,p,i;
for (p = 1; p < N; p++)
{
tmp = *(pointer+p);
for (i = p; i > 0 && *(pointer + i-1) > tmp; i--)
*(pointer + i) = *(pointer + i-1);
*(pointer + i ) = tmp;
}
}
14556799
復雜度拿到的牌剛好順序的時候O(n),逆序的時候O(n的平方)
插入排序演算法也穩定,因為只有絕對不等的時候才換位置,
3時間復雜度下屆
- 逆序對
與線性代數的概念差不多,這里是說如果i>j,A[i]<A[j],這就說(i,j)是一個逆序對,
因為每組資料的逆序對總數不變,那么只要是以每次消去一個逆序對進行排序的演算法的次數都是相同的,
冒泡排序和插入排序每次交換一個逆序對 - 插入排序復雜度
O(N+I),N為初始元素個數,I為逆序對個數; - 任意N個不同元素的逆序對平均具有N(N-1)/4個逆序對,任何僅以交換逆序對兩元素來排序的演算法,平均復雜度為 Ω \Omega Ω(N平方), Ω \Omega Ω表示下屆 , O表示上界, Θ \Theta Θ表示下屆和上界
4希爾排序
上邊的冒泡排序和插入排序每次只交換一個逆序對,所以效率較低,為了提高效率,可以跟換交換的方法
- 定義增量序列,比如說5,3,1;對每個數字進行間隔排序,意思就是首先5-間隔排序,然后3-間隔排序,最后1-間隔排序,
例子如下

偽代碼
void Shell_sort(int A[], int N)
{
for (D = N / 2; D > 0; D = D / 2 )
{
for (p = D; p < N; p++)
{
tmp =A[p];
for (i = p; i > 0 && A[i-D] > tmp; i -= D)
{
A[i]=A[i-D];
}
A[i]= tmp;
}
}
}
代碼實作
#include<stdio.h>
int count=0;
int main()
{
void paixu_3(int* point, int N);
int i;
int arr[8] = { 1,9,6,4,5,6,7,9};
paixu_3(arr, 8);
for (i = 0; i < 8; i++)
{
printf("%d", arr[i]);
}
printf("\n%d",count);
return 0;
}
void paixu_3(int* point, int N)
{
int p, D, tmp, i;
for (D = N / 2; D > 0; D=D/2)
{
for (p = D; p < N; p++)
{
tmp = *(point + p);
for (i = p; i > 0 && *(point + i - D) > tmp; i -= D)
{
*(point + i) = *(point + i - D);
count++;
}
*(point + i) = tmp;
}
}
}
14566799
4
Hibbard序列
對于上邊最基礎的增量系列,可能出現復雜度為
Θ
\Theta
Θ(n平方)表示下屆和上界,因為增量元素不互質,比如說為8,4,2,1;如果這樣的話可能會出現小增量根本不起作用

為了克服這個問題,提出了 Hibbard序列

5選擇排序
選擇排序原理
- 在陣列無序部分找到最小元素,然后把他放到有序部分的最后位置
偽代碼
void Selection_Sort(ElementType A[],int N)
{
for(i=0;i<N;i++)
{
MinPosition=ScanFormin(A,i,N-1);
Swap(A[i],A[Minposition]);
}
}
代碼實作
#include<stdio.h>
int main()
{
void Selection_Sort(int* p1, int N);
int A[20] = { 5,8,7,9,4,5,6,3,15,15,66,48,41,15,16,11,5,1,9,20 };
Selection_Sort(A, 20);
for(int i=0;i<20;i++)
printf("%3d",A[i]);
return 0;
}
void Selection_Sort(int *p1, int N)
{
void swap(int* m, int* n);
int i,MinPosition;
void ScanForMin(int* p2, int k, int end_num);
for (i = 0; i < N; i++)
{
ScanForMin(p1, i, N - 1);
swap((p1+i), (p1+N-1));
}
}
void ScanForMin(int *p2, int k, int end_num)//冒泡演算法求最小值
{
int i;
void swap(int* m, int* n);
for (int i = k; i <= end_num; i++)
if (*(p2+i) < *(p2 + i + 1))
swap((p2 + i), (p2 + i + 1));
}
void swap(int *m, int *n)
{
int temp;
temp = *m;
*m = *n;
*n = temp;
}
1 3 4 5 5 5 6 7 8 9 9 11 15 15 15 16 20 41 48 66
- 這個提取無序部分最小值采用的方法是冒泡排序,發現沒有,先冒泡找到無序的最小值,然后放到有序的最后,好像更加復雜了哈,下面就是尋找無需部分最小元素的好方法,最大,最大堆,最小堆
6堆排序
尋找最小元,最大元
堆排序基礎程式(堆的建立,插入,洗掉)
這里說的是抽象資料結構堆是 基于資料物件集為完全二叉樹建立的堆,
堆就是一個特殊的二叉樹,最大堆就是結點元素大于左右兒子所有元的完全二叉樹
基本思想:按陣列元素的順序以此插入樹,然后調整樹的結點完成最大最自小堆的建立,通過每次取出(洗掉)最大結點完成排序,
==復雜度是線性復雜度 ==
typedef struct HNode *Heap; /* 堆的型別定義 */
struct HNode {
ElementType *Data; /* 存盤元素的陣列 */
int Size; /* 堆中當前元素個數 */
int Capacity; /* 堆的最大容量 */
};
typedef Heap MaxHeap; /* 最大堆 */
typedef Heap MinHeap; /* 最小堆 */
#define MAXDATA 1000 /* 該值應根據具體情況定義為大于堆中所有可能元素的值 */
MaxHeap CreateHeap( int MaxSize )
{ /* 創建容量為MaxSize的空的最大堆 */
MaxHeap H = (MaxHeap)malloc(sizeof(struct HNode));
H->Data = (ElementType *)malloc((MaxSize+1)*sizeof(ElementType));
H->Size = 0;
H->Capacity = MaxSize;
H->Data[0] = MAXDATA; /* 定義"哨兵"為大于堆中所有可能元素的值*/
return H;
}
bool IsFull( MaxHeap H )
{
return (H->Size == H->Capacity);
}
bool Insert( MaxHeap H, ElementType X )
{ /* 將元素X插入最大堆H,其中H->Data[0]已經定義為哨兵 */
int i;
if ( IsFull(H) ) {
printf("最大堆已滿");
return false;
}
i = ++H->Size; /* i指向插入后堆中的最后一個元素的位置 */
for ( ; H->Data[i/2] < X; i/=2 )
H->Data[i] = H->Data[i/2]; /* 上濾X */
H->Data[i] = X; /* 將X插入 */
return true;
}
#define ERROR -1 /* 錯誤標識應根據具體情況定義為堆中不可能出現的元素值 */
bool IsEmpty( MaxHeap H )
{
return (H->Size == 0);
}
ElementType DeleteMax( MaxHeap H )
{ /* 從最大堆H中取出鍵值為最大的元素,并洗掉一個結點 */
int Parent, Child;
ElementType MaxItem, X;
if ( IsEmpty(H) ) {
printf("最大堆已為空");
return ERROR;
}
MaxItem = H->Data[1]; /* 取出根結點存放的最大值 */
/* 用最大堆中最后一個元素從根結點開始向上過濾下層結點 */
X = H->Data[H->Size--]; /* 注意當前堆的規模要減小 */
for( Parent=1; Parent*2<=H->Size; Parent=Child ) {
Child = Parent * 2;
if( (Child!=H->Size) && (H->Data[Child]<H->Data[Child+1]) )
Child++; /* Child指向左右子結點的較大者 */
if( X >= H->Data[Child] ) break; /* 找到了合適位置 */
else /* 下濾X */
H->Data[Parent] = H->Data[Child];
}
H->Data[Parent] = X;
return MaxItem;
}
/*----------- 建造最大堆 -----------*/
void PercDown( MaxHeap H, int p )
{ /* 下濾:將H中以H->Data[p]為根的子堆調整為最大堆 */
int Parent, Child;
ElementType X;
X = H->Data[p]; /* 取出根結點存放的值 */
for( Parent=p; Parent*2<=H->Size; Parent=Child ) {
Child = Parent * 2;
if( (Child!=H->Size) && (H->Data[Child]<H->Data[Child+1]) )
Child++; /* Child指向左右子結點的較大者 */
if( X >= H->Data[Child] ) break; /* 找到了合適位置 */
else /* 下濾X */
H->Data[Parent] = H->Data[Child];
}
H->Data[Parent] = X;
}
void BuildHeap( MaxHeap H )
{ /* 調整H->Data[]中的元素,使滿足最大堆的有序性 */
/* 這里假設所有H->Size個元素已經存在H->Data[]中 */
int i;
/* 從最后一個結點的父節點開始,到根結點1 */
for( i = H->Size/2; i>0; i-- )
PercDown( H, i );
}
堆排序演算法1(核心程式)
void Heap_Sort (ElementType A[],int N)
{
BuildHeap(A);//建立最小堆
for(i=0;i<N;i++)
TmpA[i]=DeleteMin(A);
for(i=0;i<N;i++)
A[i]=Temp[i];
}
堆排序演算法1代碼實體
#include<stdio.h>
#include<stdbool.h>
#define ERROR -1 /* 錯誤標識應根據具體情況定義為堆中不可能出現的元素值 */
typedef struct HNode* Heap; //指向結構體(堆)的指標
struct HNode//用陣串列示的二叉樹表示堆
{
int* Data; /* 存盤元素的陣列 */
int Size; /* 堆中當前元素個數 */
int Capacity; /* 堆的最大容量 */
};
typedef Heap MaxHeap; /* 最大堆 */
#define MAXDATA 1000 /* 該值應根據具體情況定義為大于堆中所有可能元素的值 */
//創建容量為MAXSize的空堆
MaxHeap CreateHeap(int MaxSize)
{
MaxHeap H = (MaxHeap)malloc(sizeof(struct HNode));//H指向儲存單元的首地址
H->Data = (int*)malloc((MaxSize) * sizeof(int));
H->Size = 0;
H->Capacity = MaxSize;
H->Data[0] = MAXDATA; /* 定義"哨兵"為大于堆中所有可能元素的值*/
return H;
}
bool IsFull(MaxHeap H)
{
return (H->Size == H->Capacity);
}
void Insert(MaxHeap H, int X)
{ /* 將元素X插入最大堆H,其中H->Data[0]已經定義為哨兵 */
int i;
if (IsFull(H)) {
printf("最大堆已滿");
}
i = ++H->Size; /* i指向插入后堆中的最后一個元素的位置 */
for (; H->Data[i / 2] < X; i /= 2)
H->Data[i] = H->Data[i / 2]; /* 上濾X */
H->Data[i] = X; /* 將X插入 */
}
bool IsEmpty(MaxHeap H)
{
return (H->Size == 0);
}
int DeleteMax(MaxHeap H)
{ /* 從最大堆H中取出鍵值為最大的元素,并洗掉一個結點 */
int Parent, Child;
int MaxItem, X;
if (IsEmpty(H)) {
printf("最大堆已為空");
return ERROR;
}
MaxItem = H->Data[1]; /* 取出根結點存放的最大值 */
/* 用最大堆中最后一個元素從根結點開始向上過濾下層結點 */
X = H->Data[H->Size--]; /* 注意當前堆的規模要減小 */
for (Parent = 1; Parent * 2 <= H->Size; Parent = Child) {
Child = Parent * 2;
if ((Child != H->Size) && (H->Data[Child] < H->Data[Child + 1]))
Child++; /* Child指向左右子結點的較大者 */
if (X >= H->Data[Child]) break; /* 找到了合適位置 */
else /* 下濾X */
H->Data[Parent] = H->Data[Child];
}
H->Data[Parent] = X;
return MaxItem;
}
/*----------- 建造最大堆 -----------*/
void PercDown(MaxHeap H, int p)
{ /* 下濾:將H中以H->Data[p]為根的子堆調整為最大堆 */
int Parent, Child;
int X;
X = H->Data[p]; /* 取出根結點存放的值 */
for (Parent = p; Parent * 2 <= H->Size; Parent = Child) {
Child = Parent * 2;
if ((Child != H->Size) && (H->Data[Child] < H->Data[Child + 1]))
Child++; /* Child指向左右子結點的較大者 */
if (X >= H->Data[Child]) break; /* 找到了合適位置 */
else /* 下濾X */
H->Data[Parent] = H->Data[Child];
}
H->Data[Parent] = X;
}
void BuildHeap(MaxHeap H)//H是結構體指標變數
{ /* 調整H->Data[]中的元素,使滿足最大堆的有序性 */
/* 這里假設所有H->Size個元素已經存在H->Data[]中 */
int i;
/* 從最后一個結點的父節點開始,到根結點1 */
for (i = H->Size / 2; i > 0; i--)
PercDown(H, i);
}
void paixu_heap(int *A, int N)
{
int i;
MaxHeap H_1;
int TmpA[16];
H_1 = CreateHeap(16);
for (i =1; i < 16; i++)
{
Insert(H_1, *(A+i));
}
BuildHeap(H_1);
for (i = 1; i < N; i++)
A[i] = DeleteMax(H_1);
// TmpA[i] = DeleteMax(H_1);
//for (i = 0; i < N; i++)
// A[i] = TmpA[i];
}
int main()
{
int arr[16] = { MAXDATA,1, 6, 8, 4, 8, 9, 1, 12, 66, 78, 12, 1, 6, 9, 5 };
paixu_heap(arr, 16);
for (int i = 1; i < 16; i++)
{
printf("%d ", arr[i]);
}
return 0;
}
78 66 12 12 9 9 8 8 6 6 5 4 1 1 1
7有序子列的歸并
把兩個子數列按順序放進一個陣列,用這中思想可以加快排序的速度,
可以把一個陣列分開,然后采用這種思路進行排序,叫做歸并排序
歸并演算法代碼實作
//歸并排序
#include<stdio.h>
int main()
{
void Merge_sort(int* p, int N);
int a[10] = { 1,5,9,7,5,3,2,4,6,8 };
int* point;
point = a;
Merge_sort(point, 10);
for (int i = 0; i < 10; i++)
printf("%d ", *(point+i));
return 0;
}
void Merge(int *p2, int *pb2, int L, int R, int RightEnd)
{
int LeftEnd = R - 1;
int Tmp = L;
int NumElements = RightEnd-L + 1;
while (L <= LeftEnd && R <= RightEnd)
{
if (*(p2 + L) <= *(p2 + R))
{
*(pb2+Tmp) = *(p2 + L);
Tmp++;
L++;
}
else
{
*(pb2 + Tmp) = *(p2 + R);
Tmp++;
R++;
}
}
while (L <= LeftEnd)
{
*(pb2 + Tmp) = *(p2 + L);
Tmp++;
L++;
}
while (R <= RightEnd)
{
*(pb2 + Tmp) = *(p2 + R);
Tmp++;
R++;
}
for (int i = 0; i < NumElements; i++,RightEnd--)
{
*(p2 + RightEnd) = *(pb2 + RightEnd);
}
}
void Msort(int *p0, int *pb, int L, int RightEnd)
{
int center;
if (L < RightEnd)
{
center = (L + RightEnd) / 2;
Msort(p0, pb, L, center);
Msort(p0, pb, center + 1, RightEnd);
Merge(p0, pb, L, center +1, RightEnd);
}
}
void Merge_sort(int *p, int N)
{
int* tmpA;
tmpA = (int*)malloc(N * sizeof(int));
if (tmpA != NULL)
{
Msort(p, tmpA, 0, N - 1);
free(tmpA);
}
else
printf("空間不足");
}
1 2 3 4 5 6 7 8 9
另外桶排序和表排序在下一篇:排序2
轉載請註明出處,本文鏈接:https://www.uj5u.com/qita/282706.html
標籤:其他
