編程必備！9種排序的實(shí)現(xiàn)

時間：2019-03-27 09:24:01

關(guān)鍵字：排序編程

手機(jī)看文章

掃描二維碼
隨時隨地手機(jī)看文章

[導(dǎo)讀]#includevoid PrintData(int *pDataArray, int iDataNum){?for (int i = 0; i < iDataNum; i++)??printf

#include

void PrintData(int *pDataArray, int iDataNum)
{
?for (int i = 0; i < iDataNum; i++)
??printf("%d ", pDataArray[i]);
?printf("n");
?fflush(stdout);
}

//交換data1和data2所指向的整形
void DataSwap(int* data1, int* data2)
{
?int temp = *data1;
?*data1 = *data2;
?*data2 = temp;
}

/********************************************************
*函數(shù)名稱：ShellInsert
*參數(shù)說明：pDataArray 無序數(shù)組；
*????????? d????????? 增量大小
*???? iDataNum為無序數(shù)據(jù)個數(shù)
*說明：??? 希爾按增量d的插入排序
*********************************************************/
void ShellInsert(int* pDataArray, int d, int iDataNum)
{
?for (int i = d; i < iDataNum; i += 1)??? //從第2個數(shù)據(jù)開始插入
?{
??int j = i - d;
??int temp = pDataArray[i];??? //記錄要插入的數(shù)據(jù)
??while (j >= 0 && pDataArray[j] > temp)??? //從后向前，找到比其小的數(shù)的位置
??{
???pDataArray[j+d] = pDataArray[j];??? //向后挪動
???j -= d;
??}

??if (j != i - d)??? //存在比其小的數(shù)
???pDataArray[j+d] = temp;
?}
}

/********************************************************
*函數(shù)名稱：ShellSort
*參數(shù)說明：pDataArray 無序數(shù)組；
*???? iDataNum為無序數(shù)據(jù)個數(shù)
*說明：??? 希爾排序
*********************************************************/
void ShellSort(int* pDataArray, int iDataNum)
{
?int d = iDataNum / 2;??? //初始增量設(shè)為數(shù)組長度的一半
?while(d >= 1)
?{
??ShellInsert(pDataArray, d, iDataNum);
??d = d / 2;??? //每次增量變?yōu)樯洗蔚亩种?br />?}
}

/********************************************************
*函數(shù)名稱：GetNumInPos
*參數(shù)說明：num 一個整形數(shù)據(jù)
*???? pos 表示要獲得的整形的第pos位數(shù)據(jù)
*說明：??? 找到num的從低到高的第pos位的數(shù)據(jù)
*********************************************************/
int GetNumInPos(int num,int pos)
{
?int temp = 1;
?for (int i = 0; i < pos - 1; i++)
??temp *= 10;

?return (num / temp) % 10;
}

/********************************************************
*函數(shù)名稱：RadixSort
*參數(shù)說明：pDataArray 無序數(shù)組；
*???? iDataNum為無序數(shù)據(jù)個數(shù)
*說明：??? 基數(shù)排序
*********************************************************/
#define RADIX_10 10??? //整形排序
#define KEYNUM_31 10???? //關(guān)鍵字個數(shù)，這里為整形位數(shù)
void RadixSort(int* pDataArray, int iDataNum)
{
?int *radixArrays[RADIX_10];??? //分別為0~9的序列空間
?for (int i = 0; i < 10; i++)
?{
??radixArrays[i] = (int *)malloc(sizeof(int) * (iDataNum + 1));
??radixArrays[i][0] = 0;??? //index為0處記錄這組數(shù)據(jù)的個數(shù)
?}

?for (int pos = 1; pos <= KEYNUM_31; pos++)??? //從個位開始到31位
?{
??for (int i = 0; i < iDataNum; i++)??? //分配過程
??{
???int num = GetNumInPos(pDataArray[i], pos);
???int index = ++radixArrays[num][0];
???radixArrays[num][index] = pDataArray[i];
??}

??for (int i = 0, j =0; i < RADIX_10; i++)??? //收集
??{
???for (int k = 1; k <= radixArrays[i][0]; k++)
????pDataArray[j++] = radixArrays[i][k];
???radixArrays[i][0] = 0;??? //復(fù)位
??}
?}
}

/********************************************************
*函數(shù)名稱：SlipDown
*參數(shù)說明：pDataArray 無序數(shù)組；
*???? iCurNode為堆中需要調(diào)整的節(jié)點(diǎn)
*????????? iDataNum為數(shù)組長度
*函數(shù)返回：分割后的分割數(shù)位置
*函數(shù)說明：調(diào)整iCurNode處的節(jié)點(diǎn)，形成大頂堆???
*********************************************************/
void SlipDown(int *pDataArray,int iCurNode,int iDataNum)
{
?int temp = pDataArray[iCurNode];??? //記錄需要調(diào)整的節(jié)點(diǎn)值

?for (int iNextNode = iCurNode*2; iNextNode <= iDataNum; iNextNode = iCurNode*2)
?{
??if (iNextNode + 1 <= iDataNum
???&& pDataArray[iNextNode] < pDataArray[iNextNode + 1])??? //尋找iCurNode子節(jié)點(diǎn)中的大者
???iNextNode++;
??if (pDataArray[iNextNode] > temp)??? //大的值上移
???pDataArray[iCurNode] = pDataArray[iNextNode];???
??else??? //結(jié)束調(diào)整
???break;

??iCurNode = iNextNode;??? //更新需要調(diào)整的節(jié)點(diǎn)
?}

?pDataArray[iCurNode] = temp;
}

/********************************************************
*函數(shù)名稱：HeapSort
*參數(shù)說明：pDataArray 無序數(shù)組；
*???? iDataNum為無序數(shù)據(jù)個數(shù)
*說明：??? 堆排序
*********************************************************/
void HeapSort(int* pDataArray, int iDataNum)
{
?pDataArray--;??? //讓原先數(shù)組下標(biāo)0對應(yīng)1，便于堆中節(jié)點(diǎn)的訪問
?for (int i = iDataNum/2; i > 0; i--)??? //調(diào)整為大頂堆
??SlipDown(pDataArray, i, iDataNum);

?for (int i = iDataNum; i > 1; i--)??? //根據(jù)大頂堆進(jìn)行排序
?{
??DataSwap(&pDataArray[i], &pDataArray[1]);
??SlipDown(pDataArray, 1, i - 1);
?}
}

/********************************************************
*函數(shù)名稱：Split
*參數(shù)說明：pDataArray 無序數(shù)組；
*???? iBegin為pDataArray需要快速排序的起始位置
*????????? iEnd為pDataArray需要快速排序的結(jié)束位置
*函數(shù)返回：分割后的分割數(shù)位置
*說明：??? 以iBegin處的數(shù)值value作為分割數(shù)，
使其前半段小于value，后半段大于value
*********************************************************/
int Split(int *pDataArray,int iBegin,int iEnd)
{
?int rIndex = rand() % (iEnd - iBegin + 1);??? //隨機(jī)獲得偏移位置

?int pData = pDataArray[iBegin + rIndex];??? //將iBegin+rIndex處的值作為劃分值

?while (iBegin < iEnd)??? //循環(huán)分割數(shù)組，使其前半段小于pData，后半段大于pData
?{
??while (iEnd > iBegin && pDataArray[iEnd] >= pData)??? //從后向前尋找小于pData的數(shù)據(jù)位置
???iEnd--;

??if (iEnd != iBegin)
??{
???pDataArray[iBegin] = pDataArray[iEnd];??? //將小于pData數(shù)據(jù)存放到數(shù)組前方
???iBegin++;

???while (iBegin < iEnd && pDataArray[iBegin] <= pData)
????iBegin++;

???if (iBegin != iEnd)
???{
????pDataArray[iEnd] = pDataArray[iBegin];??? //將大于pData數(shù)據(jù)存放到數(shù)組后方
????iEnd--;
???}
??}
?}

?pDataArray[iEnd] = pData;??? //此時iBegin=iEnd，此處存儲分割數(shù)據(jù)pData
?return iEnd;
}

/********************************************************
*函數(shù)名稱：QSort
*參數(shù)說明：pDataArray 無序數(shù)組；
*???? iBegin為pDataArray需要快速排序的起始位置
*????????? iEnd為pDataArray需要快速排序的結(jié)束位置
*說明：??? 快速排序遞歸函數(shù)
*********************************************************/
void QSort(int* pDataArray, int iBegin, int iEnd)
{
?if (iBegin < iEnd)
?{
??int pos = Split(pDataArray, iBegin, iEnd);??? //獲得分割后的位置
??QSort(pDataArray, iBegin, pos - 1);?????????? //對分割后的前半段遞歸快排
??QSort(pDataArray, pos + 1, iEnd);???????????? //對分割后的后半段遞歸快排
?}
}

/********************************************************
*函數(shù)名稱：QuickSort
*參數(shù)說明：pDataArray 無序數(shù)組；
*???? iDataNum為無序數(shù)據(jù)個數(shù)
*說明：??? 快速排序
*********************************************************/
void QuickSort(int* pDataArray, int iDataNum)
{
?QSort(pDataArray, 0, iDataNum - 1);
}

/********************************************************
*函數(shù)名稱：Merge
*參數(shù)說明：pDataArray 無序數(shù)組；
*????????? int *pTempArray 臨時存儲合并后的序列
*????????? bIndex 需要合并的序列1的起始位置
*????????? mIndex 需要合并的序列1的結(jié)束位置
并且作為序列2的起始位置
*????????? eIndex 需要合并的序列2的結(jié)束位置
*說明：??? 將數(shù)組中連續(xù)的兩個子序列合并為一個有序序列
*********************************************************/
void Merge(int* pDataArray, int *pTempArray, int bIndex, int mIndex, int eIndex)
{
?int mLength = eIndex - bIndex;??? //合并后的序列長度
?int i = 0;??? //記錄合并后序列插入數(shù)據(jù)的偏移
?int j = bIndex;??? //記錄子序列1插入數(shù)據(jù)的偏移
?int k = mIndex;??? //記錄子序列2摻入數(shù)據(jù)的偏移

?while (j < mIndex && k < eIndex)
?{
??if (pDataArray[j] <= pDataArray[k])
??{
???pTempArray[i++] = pDataArray[j];
???j++;
??}
??else
??{
???pTempArray[i++] = pDataArray[k];
???k++;
??}
?}

?if (j == mIndex)??? //說明序列1已經(jīng)插入完畢
??while (k < eIndex)
???pTempArray[i++] = pDataArray[k++];
?else??????????????? //說明序列2已經(jīng)插入完畢
??while (j < mIndex)
???pTempArray[i++] = pDataArray[j++];

?for (i = 0; i < mLength; i++)??? //將合并后序列重新放入pDataArray
??pDataArray[bIndex + i] = pTempArray[i];
}

/********************************************************
*函數(shù)名稱：BottomUpMergeSort
*參數(shù)說明：pDataArray 無序數(shù)組；
*???? iDataNum為無序數(shù)據(jù)個數(shù)
*說明：??? 自底向上的歸并排序
*********************************************************/
void BottomUpMergeSort(int* pDataArray, int iDataNum)
{
?int *pTempArray = (int *)malloc(sizeof(int) * iDataNum);??? //臨時存放合并后的序列
?int length = 1;??? //初始有序子序列長度為1
?while (length < iDataNum)
?{
??int i = 0;
??for (; i + 2*length < iDataNum; i += 2*length)
???Merge(pDataArray, pTempArray, i, i + length, i + 2*length);
??if (i + length < iDataNum)
???Merge(pDataArray, pTempArray, i, i + length, iDataNum);
??length *= 2;??? //有序子序列長度*2
?}
?free(pTempArray);
}

/********************************************************
*函數(shù)名稱：RecursionMergeSort
*參數(shù)說明：pDataArray 無序數(shù)組；
*????????? int *pTempArray 臨時存放合并的序列
*???? iBegin為pDataArray需要?dú)w并排序的起始位置
*????????? iEnd為pDataArray需要?dú)w并排序的結(jié)束位置
*說明：??? 自頂向下的歸并排序遞歸函數(shù)
*********************************************************/
void RecursionMergeSort(int* pDataArray, int *pTempArray, int iBegin, int iEnd)
{
?if (iBegin < iEnd)
?{
??int middle = (iBegin + iEnd) / 2;
??RecursionMergeSort(pDataArray, pTempArray, iBegin, middle);??? //前半段遞歸歸并排序
??RecursionMergeSort(pDataArray, pTempArray, middle + 1, iEnd);? //后半段歸并排序
??Merge(pDataArray, pTempArray, iBegin, middle + 1, iEnd + 1);?? //合并前半段和后半段
?}
}

/********************************************************
*函數(shù)名稱：UpBottomMergeSort
*參數(shù)說明：pDataArray 無序數(shù)組；
*???? iDataNum為無序數(shù)據(jù)個數(shù)
*說明：??? 自頂向下的歸并排序
*********************************************************/
void UpBottomMergeSort(int* pDataArray, int iDataNum)
{
?int *pTempArray = (int *)malloc(sizeof(int) * iDataNum);??? //臨時存放合并后的序列
?RecursionMergeSort(pDataArray, pTempArray, 0, iDataNum - 1);
?free(pTempArray);
}

//查找數(shù)值iData在長度為iLen的pDataArray數(shù)組中的插入位置
int FindInsertIndex(int *pDataArray, int iLen, int iData)
{
?int iBegin = 0;
?int iEnd = iLen - 1;
?int index = -1;??? //記錄插入位置
?while (iBegin <= iEnd)
?{
??index = (iBegin + iEnd) / 2;
??if (pDataArray[index] > iData)
???iEnd = index - 1;
??else
???iBegin = index + 1;
?}
?if (pDataArray[index] <= iData)
??index++;
?return index;
}

/********************************************************
*函數(shù)名稱：BinaryInsertSort
*參數(shù)說明：pDataArray 無序數(shù)組；
*???? iDataNum為無序數(shù)據(jù)個數(shù)
*說明：??? 二分查找插入排序
*********************************************************/
void BinaryInsertSort(int* pDataArray, int iDataNum)
{
?for (int i = 1; i < iDataNum; i++)??? //從第2個數(shù)據(jù)開始插入
?{
??int index = FindInsertIndex(pDataArray, i, pDataArray[i]);??? //二分尋找插入的位置

??if (i != index)??? //插入位置不為i，才挪動、插入
??{
???int j = i;
???int temp = pDataArray[i];
???while (j > index)??? //挪動位置
???{
????pDataArray[j] = pDataArray[j-1];
????j--;
???}
???pDataArray[j] = temp;??? //插入
??}
?}
}

/********************************************************
*函數(shù)名稱：InsertSort
*參數(shù)說明：pDataArray 無序數(shù)組；
*???? iDataNum為無序數(shù)據(jù)個數(shù)
*說明：??? 插入排序（從前向后尋找）
*********************************************************/
void InsertSort(int* pDataArray, int iDataNum)
{
?for (int i = 1; i < iDataNum; i++)??? //從第2個數(shù)據(jù)開始插入
?{
??int j = 0;
??while (j < i && pDataArray[j] <= pDataArray[i])??? //尋找插入的位置
???j++;

??if (j < i)??? //i位置之前，有比pDataArray[i]大的數(shù)，則進(jìn)行挪動和插入
??{
???int k = i;
???int temp = pDataArray[i];
???while (k > j)??? //挪動位置
???{
????pDataArray[k] = pDataArray[k-1];
????k--;
???}
???pDataArray[k] = temp;??? //插入
??}
?}
}

/********************************************************
*函數(shù)名稱：InsertSort
*參數(shù)說明：pDataArray 無序數(shù)組；
*???? iDataNum為無序數(shù)據(jù)個數(shù)
*說明：??? 插入排序（從后向前尋找）
*********************************************************/
void InsertSort1(int* pDataArray, int iDataNum)
{
?for (int i = 1; i < iDataNum; i++)??? //從第2個數(shù)據(jù)開始插入
?{
??int j = i - 1;
??int temp = pDataArray[i];??? //記錄要插入的數(shù)據(jù)
??while (j >= 0 && pDataArray[j] > temp)??? //從后向前，找到比其小的數(shù)的位置
??{
???pDataArray[j+1] = pDataArray[j];??? //向后挪動
???j--;
??}

??if (j != i - 1)??? //存在比其小的數(shù)
???pDataArray[j+1] = temp;
?}
}

/********************************************************
*函數(shù)名稱：SelectionSort
*參數(shù)說明：pDataArray 無序數(shù)組；
*???? iDataNum為無序數(shù)據(jù)個數(shù)
*說明：??? 選擇排序
*********************************************************/
void SelectionSort(int* pDataArray, int iDataNum)
{
?for (int i = 0; i < iDataNum - 1; i++)??? //從第一個位置開始
?{
??int index = i;
??for (int j = i + 1; j < iDataNum; j++)??? //尋找最小的數(shù)據(jù)索引
???if (pDataArray[j] < pDataArray[index])
????index = j;

??if (index != i)??? //如果最小數(shù)位置變化則交換
???DataSwap(&pDataArray[index], &pDataArray[i]);
?}
}

/********************************************************
*函數(shù)名稱：BubbleSort
*參數(shù)說明：pDataArray 無序數(shù)組；
*???? iDataNum為無序數(shù)據(jù)個數(shù)
*說明：??? 冒泡排序
*********************************************************/
void BubbleSort(int* pDataArray, int iDataNum)
{
?BOOL flag = FALSE;??? //記錄是否存在交換
?for (int i = 0; i < iDataNum - 1; i++)??? //走iDataNum-1趟
?{
??flag = FALSE;
??for (int j = 0; j < iDataNum - i - 1; j++)???
???if (pDataArray[j] > pDataArray[j + 1])
???{
????flag = TRUE;
????DataSwap(&pDataArray[j], &pDataArray[j + 1]);
???}

???if (!flag)??? //上一趟比較中不存在交換，則退出排序
????break;
?}
}

//測試序列是否有序
BOOL CheckOrder(int *pDataArray, int iDataNum)
{
?for (int i = 0; i < iDataNum -? 1; i++)
??if (pDataArray[i] > pDataArray[i+1])
???return FALSE;
?return TRUE;
}

UINT64 time_fre;??? //時鐘頻率

UINT64 GetTimeM()
{
?//獲取當(dāng)前時間
?LARGE_INTEGER curCounter;
?QueryPerformanceCounter(&curCounter);
?return curCounter.QuadPart*1000/time_fre;
}

void BubbleSortTest(int *pDataArray,int length, FILE *fp)
{
?//初始化數(shù)組
?for (int i = 0; i < length; i++)
??pDataArray[i] = rand()%100000;

?UINT64 begin;
?UINT64 end;
?begin = GetTimeM();
?BubbleSort(pDataArray, length);
?end = GetTimeM();