国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

首頁 > 學院 > 開發設計 > 正文

常用排序算法小結

2019-11-08 02:26:49
字體：大 中 小
來源：轉載
供稿：網友

好用常用的排序算法

標簽（空格分隔）： 算法學習

常見的八大排序算法：插入排序，選擇排序，堆排序，快速排序，冒泡排序，歸并排序，希爾排序，基數排序。其中筆者常用的排序算法：對于數據量較小通常采用插入排序，數據量較大選擇快速排序，數據量較大且要求穩定性通常選擇歸并排序。

1、插入排序

1.1 算法原理：插入排序就是每一步都將一個待排數據按其大小插入到已經排序的數據中的適當位置，直到全部插入完畢。（類比打撲克牌接牌是的插入順序一樣）

1.2 C++代碼

#include<iostream>#include<stdlib.h>void insertSort(int *pointer, int length);int main(){ int a[100]; //產生1-100的隨機數 for (int i = 0; i < 100; i++) { a[i] = rand()%100; } 2、快速排序

2.1 算法原理:快速排序是找出一個元素（理論上可以隨便找一個）作為基準(pivot),然后對數組進行分區操作,使基準左邊元素的值都不大于基準值,基準右邊的元素值 都不小于基準值，如此作為基準的元素調整到排序后的正確位置。遞歸快速排序，將其他n-1個元素也調整到排序后的正確位置。最后每個元素都是在排序后的正 確位置，排序完成。所以快速排序算法的核心算法是分區操作，即如何調整基準的位置以及調整返回基準的最終位置以便分治遞歸。

2.2 C++代碼

#include <iostream>#include <stdlib.h>#include <malloc.h>#include <time.h>#include<fstream>#define N (1024*1024)using namespace std;void PrintArr(int *pnArr, int nLen){ for (int i = 0; i < nLen; i++) { printf("%d ", pnArr[i]); } printf("/n");}void Swap(int *p1, int *p2){ int nTmp = *p1; *p1 = *p2; *p2 = nTmp;}//實現對子數組[nLeft - nRight]的原址重排，將主元素放到合適位置//遞增排序int Patition1(int *pnArr, int nLeft, int nRight){ int nKey = pnArr[nRight]; int i = nLeft - 1; for (int j = nLeft; j < nRight; j++) { if (pnArr[j] <= nKey) { i++; Swap(&pnArr[i], &pnArr[j]); } } //將主元素插入到中間位置 Swap(&pnArr[i + 1], &pnArr[nRight]); return i + 1;}//遞增排序int Patition2(int *pnArr, int nLeft, int nRight){ int nKey = nRight; int i = nLeft - 1; bool bExchange = false; for (int j = nLeft; j < nRight; j++) { if (pnArr[j] < pnArr[nKey]) { i++; Swap(&pnArr[i], &pnArr[j]); bExchange = true; } } Swap(&pnArr[i + 1], &pnArr[nRight]); if (bExchange) { return i + 1; } else { return (nLeft + nRight) / 2; }}//遞減排序int Patition3(int *pnArr, int nLeft, int nRight){ int nKey = nRight; int i = nLeft - 1; for (int j = nLeft; j < nRight; j++) { if (pnArr[j] > pnArr[nKey]) { i++; Swap(&pnArr[i], &pnArr[j]); } } Swap(&pnArr[i + 1], &pnArr[nRight]); return i + 1;}//尋找一個nTmpPos下標，nTmpPos左邊的值都小于它，右邊的值都大于它void QuickSort(int *pnArr, int nLeft, int nRight){ if (nLeft < nRight) { //分解 int nTmpPos = Patition1(pnArr, nLeft, nRight); //解決/合并 QuickSort(pnArr, nLeft, nTmpPos - 1); QuickSort(pnArr, nTmpPos + 1, nRight); }}int main(){ srand(time(NULL)); clock_t start, end; //int nArr[N]; int *nArr = (int *)malloc(sizeof(int)*N); memset(nArr, 0, sizeof(int)*N); for (int i = 0; i < N; i++) { nArr[i] = rand() % N; } //PrintArr(nArr, 10); start = clock(); QuickSort(nArr, 0, N - 1); end = clock(); cout<< "time = " << double(end - start) / CLK_TCK << "sec!" << endl; //////////////////////////////////////////////////////////////////////////將排序結果寫入到文件中///////////////////////// ofstream outFile; outFile.open("sorted.txt"); for (int i = 0; i < N - 1; i++) { outFile << nArr[i] << endl; } free(nArr); //PrintArr(nArr, 10); system("pause"); return 0;}

3、歸并排序

3.1 算法原理: 歸并排序，它采取分而治之的策略，將兩個已經排序的序列合并成一個序列的操作。

時間復雜度是Θ(nlgn)，優于插入排序算法。

算法描述 1) 申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合并后的序列 2) 設定兩個指針，最初位置分別為兩個已經排序序列的起始位置 3) 比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一位置 4) 重復步驟3直到某一指針達到序列尾 5) 將另一序列剩下的所有元素直接復制到合并序列尾 特點：歸并排序是穩定的排序.即相等的元素的順序不會改變, 速度僅次于快速排序，但較穩定。

3.2 C++代碼

#include <stdio.h>#include <stdlib.h>#include <malloc.h>#include <time.h>#include <iostream>#include<fstream>#define SCALE 200000void PrintArr(int *pnArr, int nLen){ for (int i = 0; i < nLen; i++) { printf("%d ", pnArr[i]); } printf("/n");}//合并兩個數組void Merge(int data[], int nLpos, int nRpos, int nRightEnd){ int i; int k = nLpos; int nLeftEnd = nRpos; int nTmpPos = 0; int nLen = nRightEnd - nLpos + 1; int *pnArr = (int *)malloc(sizeof(int) * nLen); ++nRpos; while (nLpos <= nLeftEnd && nRpos <= nRightEnd) { if (data[nLpos] <= data[nRpos]) { pnArr[nTmpPos++] = data[nLpos++]; } else { pnArr[nTmpPos++] = data[nRpos++]; } } //當左邊數組或者右邊數組其中之一數據完全在數組中排好序時 while (nLpos <= nLeftEnd) { pnArr[nTmpPos++] = data[nLpos++]; } while (nRpos <= nRightEnd) { pnArr[nTmpPos++] = data[nRpos++]; } nTmpPos = 0; for (i = k; i <= nRightEnd; i++) { data[i] = pnArr[nTmpPos++]; } free(pnArr);}//排序void MergeSort(int *pnArr, int nLeft, int nRight){ if (nLeft > nRight) { return; } if (nRight > nLeft) { //1分解,可分解成若干份 int nMid = (nLeft + nRight) / 2; //2解決 MergeSort(pnArr, nLeft, nMid); MergeSort(pnArr, nMid + 1, nRight); //3合并 Merge(pnArr, nLeft, nMid, nRight); }}int main() { srand(time(NULL)); //int nArr[SCALE]; int* nArr = (int *)malloc(sizeof(int)*SCALE); memset(nArr, 0, sizeof(int)*SCALE); for (int i = 0; i < SCALE; i++) { nArr[i] = rand() % SCALE; } clock_t start, end; start = clock(); /*printf("排序前:"); PrintArr(nArr, SCALE);*/ std::ofstream outFile; /*outFile.open("random.txt"); for (int i = 0; i < SCALE; i++) outFile << "nArr["<<i<<"]"<<nArr[i] << std::endl; outFile.close();*/ MergeSort(nArr, 0, SCALE-1); end = clock(); std::cout << "time = " << double(end - start) / CLK_TCK << "sec" << std::endl; /*printf("排序后:"); PrintArr(nArr, SCALE);*/ outFile.open("sorted1.txt"); for (int i = 0; i < SCALE; i++) outFile << "nArr[" << i << "]=" << nArr[i] << std::endl; outFile.close(); free(nArr); return 0;}

發表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發表
主站蜘蛛池模板： 凤城市| 于都县| 团风县| 江川县| 肃宁县| 遂川县| 枣庄市| 许昌市| 九江市| 太湖县| 乌苏市| 南宁市| 政和县| 隆林| 新密市| 涡阳县| 襄汾县| 红原县| 逊克县| 东方市| 峨山| 牡丹江市| 醴陵市| 长白| 海兴县| 抚顺县| 平阴县| 铜山县| 沁源县| 庆元县| 广德县| 宣化县| 杨浦区| 江达县| 毕节市| 寿光市| 栾城县| 澄江县| 仪征市| 腾冲县| 内乡县|