多種種排序算法c或者c++實(shí)現(xiàn)

1、/交換排序1:冒泡法#include<iostream>using namespace std;void BubbleSort(int a,int length)int temp=0;for(int i=0;i<length-1;i+) for(int j=0;j<length-1-i;j+) if(aj>aj+1)temp=aj;aj=aj+1;aj+1=temp; /冒泡排序的改進(jìn)算法：哪趟排序算法沒有進(jìn)行比較則說明已經(jīng)按順序排列，則可以不用再繼續(xù)比較#include<staio.h>void BubbleSort(int a,int length

2、)int i,j,change=1;for(i=1;i<length&&change;i+)change=0;for(j=1;j<=n-1;j+)if(aj>aj+1)temp=aj;aj=aj+1;aj+1=temp;change=1;/交換排序2:快速排序:從數(shù)列中挑出一個(gè)元素，稱為"基準(zhǔn)"（pivot）。 采用"分治"的思想/重新排敘述列，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面，所有元素比基/準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以到任邊）。在這個(gè)分割之后，/該基準(zhǔn)是它的最后位置。這個(gè)稱為分割（partition）操作。遞

3、回地（recursive）/把小于之元素的子數(shù)列和大于之元素的子數(shù)列排序。遞回的最底部情形，是數(shù)列的/大小是零或一，也就使永遠(yuǎn)都已經(jīng)被排序好了。雖然一直遞回下去，但是這個(gè)算法/總會(huì)結(jié)束，因?yàn)樵诿看蔚牡╥teration）中，它至少會(huì)把一個(gè)元素?cái)[到它最后的位置去。int Partition(int *array, int low, int high)int pivot_val = arraylow; /基準(zhǔn)int temp;while (low < high)while (low < high && arrayhigh >= pivot_val)-high;

4、 temp =arraylow;arraylow = arrayhigh;arrayhigh = temp;while (low < high && arraylow <= pivot_val)+low;temp =arrayhigh;arrayhigh = arraylow;arraylow = temp; return low; /該算法的思想是：基準(zhǔn)元素每次隨著判斷的進(jìn)行進(jìn)行元素的交換，基準(zhǔn)元素每次也參與交換 /但是最終不再交換的時(shí)候，基準(zhǔn)元素已經(jīng)交換在前后序列的中心位置，接下來只需要對分開的兩段序列進(jìn)行排序void _QuickSort(int *array

5、, int low, int high)int pivot_loc;if (low < high)pivot_loc = Partition(array, low, high);_QuickSort(array, low, pivot_loc - 1);_QuickSort(array, pivot_loc + 1, high);void QuickSort(int *array, int length)_QuickSort(array, 0, length - 1)；/交換排序的第二種思想int Partition(int *array,int low,int high)int x=a

6、rraylow;/基準(zhǔn)while(low<high)while(low<high&&arrayhigh>=x) high-;if(low<high)rlow=rhigh;low+;while(low<high&&arraylow<=x) low+;if(low<high)rhigh=rlow;high-;rlow=x; /基準(zhǔn)元素不參與交換，最終low的位置就是基準(zhǔn)元素的位置return low; void _QuickSort(int *array,int low,int high)int pivot_loc;if(l

7、ow<high) pivot_loc=Partition(array,low,high);_QuickSort(array,low,pivot_loc-1);_QuickSort(array,pivot_loc+1,high);void QuickSort(int *array,int length)_QuickSort(array,0,length-1);/選擇排序:直接選擇排序:首先在未排序序列中找到最小元素，存放到排序序列的起/始位置，然后，再從剩余未排序元素中繼續(xù)尋找最小元素，然后放到排序序列末尾。/以此類推，直到所有元素均排序完畢。void SimpleSelectionSor

8、t(int a,int length)int minnum=0,i=0,j=0,temp=0;for(i=0;i<length-1;i+)minnum=i;for(j=i;j<length;j+)if(aj<aminnum)minnum=j;temp=ai;ai=aminnum;aminnum=temp;/插入排序1:簡單插入排序: 它的工作原理是通過構(gòu)建有序序列，對于未排序數(shù)據(jù)，/在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。/插入排序在實(shí)現(xiàn)上，通常采用in-place 排序（即只需用到O(1)的額外空間的排序），/因而在從后向前掃描過程中，需要反復(fù)把已排序元素逐步向后挪

9、位，為最新元素提/供插入空間。void StraightInsertionSort(int a,int length)int temp=0,i=0,j=0;for(i=1;i<length;i+)temp = ai;/把i 之前的大于ai的元素往后移for(j = i - 1; j >= 0 && temp < aj; j-)/這邊之所以從i - 1 以后-是避免數(shù)據(jù)被覆蓋丟失aj+1 = aj; aj+1 =temp;/在合適位置安放ai,for循環(huán)中j進(jìn)行了自減/插入排序2: 二分法查找插入排序/如果比較操作的代價(jià)比交換操作大的話，可以采用二分查找法來減少

10、比較操作的樹/目。該算法可以認(rèn)為是插入排序的一個(gè)變種，稱為二分查找排序。折半插入排序所/需附加存儲(chǔ)空間和直接插入排序相同，從時(shí)間上比較，折半插入排序僅減少了關(guān)鍵/字間的比較次數(shù)，而記錄的移動(dòng)次數(shù)不變。/其實(shí)就是二分法查找與插入排序的一個(gè)結(jié)合，在已排好的字符串中用二分法查找出/那個(gè)最合適的插入位置（找到的一般是比ai小的，即將離其最近的一個(gè)下標(biāo)n），/插入位置就是n+1void BinaryInsertionSort(int *array, int length)int i, j;int temp;int low, high, mid;for (i = 1; i < length; i+)

11、temp = arrayi;low = 0;high = i - 1;while (low <= high)mid = (low + high) / 2;if (temp < arraymid)high = mid - 1;elselow = mid + 1;for (j = i - 1; j >= high + 1; j-)arrayj+1 = arrayj; /最終找到的high位置就是應(yīng)該插入的位置arrayhigh+1 = temp;/插入排序3：希爾排序：先取一個(gè)小于n的整數(shù)d1作為第一個(gè)增量，把文件的全部/記錄分成d1個(gè)組。所有距離為d1的倍數(shù)的記錄放在同一個(gè)組中

12、。先在各組內(nèi)進(jìn)行直/接插人排序；然后，取第二個(gè)增量d2<d1重復(fù)上述的分組和排序，直至所取的增量/dt=1(dt<dt-1<<d2<d1)，即所有記錄放在同一組中進(jìn)行直接插入排序?yàn)橹?。void ShellInsert(int *array, int length, int dk)int i, j;int temp;for (i = dk; i < length; i+)temp = arrayi;for (j = i - dk; j >= 0 && temp < arrayj; j -= dk)arrayj+dk = arrayj

13、; arrayj+dk =temp;void ShellSort(int *array, int length, int *gap, int count)int i;for (i = count - 1; i >= 0; i-)ShellInsert(array, length, gapi);void shellSort(int a,int length)int gap = 1,2,3,5,8,13,21,34,55,89;ShellSort(a,length,gap,9);/合并排序：歸并操作(merge)，也叫歸并算法，指的是將兩個(gè)已經(jīng)排序的序列合并成/一個(gè)序列的操作。歸并操作的工作

14、原理如下：/1.申請空間，使其大小為兩個(gè)已經(jīng)排序序列之和，該空間用來存放合并后的序列。/2.設(shè)定兩個(gè)指針，最初位置為別為兩個(gè)已經(jīng)排序序列的起始位置。/3.比較兩個(gè)指針?biāo)赶虻脑?，選擇相對小的元素放入到合并空間，并移動(dòng)指針到/下一位置。/4.重復(fù)步驟直到某一指針達(dá)到序列尾。/5.將另一序列剩下的所有元素直接復(fù)制到合并序列尾。/歸并排序具體工作原理如下（假設(shè)序列共有n個(gè)元素）：/1.將序列每相鄰兩個(gè)數(shù)字進(jìn)行歸并操作（merge），形成floor(n / 2)個(gè)序列，排序/后每個(gè)序列包含兩個(gè)元素。/2.將上述序列再次歸并，形成floor(n / 4)個(gè)序列，每個(gè)序列包含四個(gè)元素。/3.重復(fù)步驟，直

15、到所有元素排序完畢。void Merge(int array, int first, int mid, int last)int i, j = 0;int begin1 = first, end1 = mid, begin2 = mid + 1, end2 = last;int *temp = (int *)malloc(last - first + 1) * sizeof(int);if (!temp)fprintf(stderr, "n 內(nèi)存分配失敗，程序?qū)?qiáng)制退出！n");getchar();exit(1);while (begin1 <= end1 &

16、& begin2 <= end2)if (arraybegin1 < arraybegin2)tempj+ = arraybegin1; begin1+;elsetempj+ = arraybegin2; begin2+;while (begin1 <= end1)tempj+ = arraybegin1+;while(begin2 <= end2)tempj+ = arraybegin2+;for (i = 0; i < (last - first + 1); i+)arrayfirst + i = tempi;/添加在原有空間上free(temp);void _MergeSort(int *array, int first, int last)int mid;if (first < last)mid = (first + last) / 2;_MergeSort(array, first, mid);_MergeSort(array, mid + 1, last);Merge(array, first, mid, last);void MergeSort(int *array, int length)