c++版直接選擇排序法,直接插入排序法快速排序法堆排序法冒泡排序發(fā),試驗(yàn)

1、#include <iostream> using namespace std;typedef int ElemType;/直接插入排序void InsertSort ( ElemType A,int n )int i, j;ElemType x;for ( i=1; i<n; i+ )/ 進(jìn)行 n-1 次插入x = Ai;/準(zhǔn)備插入第i個(gè)元素for (戸-1; j>=0; j- )/從第i-1個(gè)開始往前找插入點(diǎn)if ( xv Aj)Aj+1=Aj;elsebreak ;Aj+1=x;/ 插入/直接選擇排序void SelectSort(ElemType A, int

2、n)int i, j, k;ElemType x;for ( i=0; i<=n-2; i+ )/每一趟選擇最小元素并與 Ai交換k=i;for (j=i+1; j<=n-1; j+)/查找最小元素的下標(biāo)if (Aj<Ak) k=j;if (k!=i) / 交換x=Ai;Ai=Ak; Ak=x;/堆排序void Sift(ElemType A,int n, int i);void CreatHeap(ElemType A, int n)int i;for ( i = (n-2)/2; i >= 0; i-)voidSift(A, n, i);Sift(ElemType

3、A,int n, int i)/調(diào)整Ai.n-1使之為一個(gè)堆/調(diào)整Ai.n-1成為一個(gè)堆（它的左右子樹已是一個(gè)堆）ElemType x=Ai;int j = 2 * i + 1;while (j <= n-1) if ( j +1 < n && Aj< Aj+1)/ j為i的左孩子/ i有左子樹Ai=x; voidj+;if ( xv Aj) Ai=Aj; i=j; j=2*i+1;elsebreak ;HeapSort(ElemType A,/使j指向左右孩子中排序碼大的孩子/將Aj上移，以便向下篩int n)/A為待排序表，n為表的長(zhǎng)度int i;Elem

4、Type x; CreatHeap(A, n);/把A建成一個(gè)堆for (i=n_1;i>=1;i_)x = A0;A0 = Ai;/第個(gè)元素與第i個(gè)元素交換Ai = x;/Sift(A, i, 0);/調(diào)整A0.i-1使之為一個(gè)堆冒泡排序void BubbleSort( ElemType A,int n )int i, j, flag;/flag為交換標(biāo)記ElemType x;for (i=1; i<=n-1; i+) /最多n-1趟排序flag=0;for (j=n-1; j>=i; j-)/假設(shè)本次沒有交換/第i趟if ( Aj< Aj-1) flag=1;/出現(xiàn)

5、交換x=Aj Aj=Aj-1; Aj-1=x;if (flag=O) return ;/快速排序 void QuickSort(ElemType A, int s, int t)/遞歸算法，對(duì)區(qū)間AsAt進(jìn)行快速排序int i=s+1, j=t;/第一個(gè)為基準(zhǔn)元素/從左到右/從右到左i+; j-;/交換基準(zhǔn)元素/處理左區(qū)間/處理右區(qū)間ElemType temp, x = As;while ( i<=j )while ( i<=j && Ai<= x ) i+;while ( i<=j && Aj>=x) j-;if ( i <

6、 j ) temp=Ai; Ai=Aj; Aj=temp;if (s!=j)As=Aj;Aj=x;if (svj-1) QuickSort(A, s, j-1);if (j+1<t) QuickSort(A, j+1, t); void main()int i,j,n,N=5;coutvv "請(qǐng)輸入個(gè)整數(shù)："；ElemType A5;for (j=O;j<N;j+)cin»Aj;coutvv "排序前為："vvendl; for (i=0;ivN;i+) coutvvAivvendl;coutvv "直接插入排序：&quo

7、t;vvendl;InsertSort (A, N );for (i=0;ivN;i+) cout«Aivvendl;/運(yùn)行結(jié)果如右cout« "直接選擇排序："vvendl;SelectSort(A, N);for (i=0;i<N;i+)coutvvAivvendl;coutvv "堆排序:"vvendl;HeapSort(A, N);for (i=0;ivN;i+)coutvvAivvendl;coutvv "冒泡排序:"vvendl;BubbleSort(A, N);for (i=0;ivN;i+)coutvvAiv