- #include <stdio.h>
- #include <stdlib.h>
- #include <windows.h>
- #include <time.h>
- void Swap(float &x, float &y)
- {
- x = x + y;
- y = x - y;
- x = x - y;
- }
- 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;
- }
- /********************************************************
- *函数名称:ShellInsert
- *参数说明:pDataArray 无序数组;
- * d 增量大小
- * iDataNum为无序数据个数
- *说明: 希尔按增量d的插入排序
- *********************************************************/
- void ShellInsert(int* pDataArray, int d, int iDataNum)
- {
- for (int i = d; i < iDataNum; i += 1) //从第2个数据开始插入
- {
- int j = i - d;
- int temp = pDataArray[i]; //记录要插入的数据
- while (j >= 0 && pDataArray[j] > temp) //从后向前,找到比其小的数的位置
- {
- pDataArray[j+d] = pDataArray[j]; //向后挪动
- j -= d;
- }
- if (j != i - d) //存在比其小的数
- pDataArray[j+d] = temp;
- }
- }
- /********************************************************
- *函数名称:ShellSort
- *参数说明:pDataArray 无序数组;
- * iDataNum为无序数据个数
- *说明: 希尔排序
- *********************************************************/
- void ShellSort(int* pDataArray, int iDataNum)
- {
- int d = iDataNum / 2; //初始增量设为数组长度的一半
- while(d >= 1)
- {
- ShellInsert(pDataArray, d, iDataNum);
- d = d / 2; //每次增量变为上次的二分之一
- }
- }
- /********************************************************
- *函数名称:GetNumInPos
- *参数说明:num 一个整形数据
- * pos 表示要获得的整形的第pos位数据
- *说明: 找到num的从低到高的第pos位的数据
- *********************************************************/
- int GetNumInPos(int num,int pos)
- {
- int temp = 1;
- for (int i = 0; i < pos - 1; i++)
- temp *= 10;
- return (num / temp) % 10;
- }
- /********************************************************
- *函数名称:RadixSort
- *参数说明:pDataArray 无序数组;
- * iDataNum为无序数据个数
- *说明: 基数排序
- *********************************************************/
- #define RADIX_10 10 //整形排序
- #define KEYNUM_31 10 //关键字个数,这里为整形位数
- 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处记录这组数据的个数
- }
- 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; //复位
- }
- }
- }
- /********************************************************
- *函数名称:SlipDown
- *参数说明:pDataArray 无序数组;
- * iCurNode为堆中需要调整的节点
- * iDataNum为数组长度
- *函数返回:分割后的分割数位置
- *函数说明:调整iCurNode处的节点,形成大顶堆
- *********************************************************/
- void SlipDown(int *pDataArray,int iCurNode,int iDataNum)
- {
- int temp = pDataArray[iCurNode]; //记录需要调整的节点值
- for (int iNextNode = iCurNode*2; iNextNode <= iDataNum; iNextNode = iCurNode*2)
- {
- if (iNextNode + 1 <= iDataNum
- && pDataArray[iNextNode] < pDataArray[iNextNode + 1]) //寻找iCurNode子节点中的大者
- iNextNode++;
- if (pDataArray[iNextNode] > temp) //大的值上移
- pDataArray[iCurNode] = pDataArray[iNextNode];
- else //结束调整
- break;
- iCurNode = iNextNode; //更新需要调整的节点
- }
- pDataArray[iCurNode] = temp;
- }
- /********************************************************
- *函数名称:HeapSort
- *参数说明:pDataArray 无序数组;
- * iDataNum为无序数据个数
- *说明: 堆排序
- *********************************************************/
- void HeapSort(int* pDataArray, int iDataNum)
- {
- pDataArray--; //让原先数组下标0对应1,便于堆中节点的访问
- for (int i = iDataNum/2; i > 0; i--) //调整为大顶堆
- SlipDown(pDataArray, i, iDataNum);
- for (int i = iDataNum; i > 1; i--) //根据大顶堆进行排序
- {
- DataSwap(&pDataArray[i], &pDataArray[1]);
- SlipDown(pDataArray, 1, i - 1);
- }
- }
- /********************************************************
- *函数名称:Split
- *参数说明:pDataArray 无序数组;
- * iBegin为pDataArray需要快速排序的起始位置
- * iEnd为pDataArray需要快速排序的结束位置
- *函数返回:分割后的分割数位置
- *说明: 以iBegin处的数值value作为分割数,
- 使其前半段小于value,后半段大于value
- *********************************************************/
- int Split(int *pDataArray,int iBegin,int iEnd)
- {
- int rIndex = rand() % (iEnd - iBegin + 1); //随机获得偏移位置
- int pData = pDataArray[iBegin + rIndex]; //将iBegin+rIndex处的值作为划分值
- while (iBegin < iEnd) //循环分割数组,使其前半段小于pData,后半段大于pData
- {
- while (iEnd > iBegin && pDataArray[iEnd] >= pData) //从后向前寻找小于pData的数据位置
- iEnd--;
- if (iEnd != iBegin)
- {
- pDataArray[iBegin] = pDataArray[iEnd]; //将小于pData数据存放到数组前方
- iBegin++;
- while (iBegin < iEnd && pDataArray[iBegin] <= pData)
- iBegin++;
- if (iBegin != iEnd)
- {
- pDataArray[iEnd] = pDataArray[iBegin]; //将大于pData数据存放到数组后方
- iEnd--;
- }
- }
- }
- pDataArray[iEnd] = pData; //此时iBegin=iEnd,此处存储分割数据pData
- return iEnd;
- }
- /********************************************************
- *函数名称:QSort
- *参数说明:pDataArray 无序数组;
- * iBegin为pDataArray需要快速排序的起始位置
- * iEnd为pDataArray需要快速排序的结束位置
- *说明: 快速排序递归函数
- *********************************************************/
- 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); //对分割后的后半段递归快排
- }
- }
- /********************************************************
- *函数名称:QuickSort
- *参数说明:pDataArray 无序数组;
- * iDataNum为无序数据个数
- *说明: 快速排序
- *********************************************************/
- void QuickSort(int* pDataArray, int iDataNum)
- {
- QSort(pDataArray, 0, iDataNum - 1);
- }
- /********************************************************
- *函数名称:Merge
- *参数说明:pDataArray 无序数组;
- * int *pTempArray 临时存储合并后的序列
- * bIndex 需要合并的序列1的起始位置
- * mIndex 需要合并的序列1的结束位置
- 并且作为序列2的起始位置
- * eIndex 需要合并的序列2的结束位置
- *说明: 将数组中连续的两个子序列合并为一个有序序列
- *********************************************************/
- void Merge(int* pDataArray, int *pTempArray, int bIndex, int mIndex, int eIndex)
- {
- int mLength = eIndex - bIndex; //合并后的序列长度
- int i = 0; //记录合并后序列插入数据的偏移
- int j = bIndex; //记录子序列1插入数据的偏移
- int k = mIndex; //记录子序列2掺入数据的偏移
- 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已经插入完毕
- while (k < eIndex)
- pTempArray[i++] = pDataArray[k++];
- else //说明序列2已经插入完毕
- while (j < mIndex)
- pTempArray[i++] = pDataArray[j++];
- for (i = 0; i < mLength; i++) //将合并后序列重新放入pDataArray
- pDataArray[bIndex + i] = pTempArray[i];
- }
- /********************************************************
- *函数名称:BottomUpMergeSort
- *参数说明:pDataArray 无序数组;
- * iDataNum为无序数据个数
- *说明: 自底向上的归并排序
- *********************************************************/
- 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);
- }
- /********************************************************
- *函数名称:RecursionMergeSort
- *参数说明:pDataArray 无序数组;
- * int *pTempArray 临时存放合并的序列
- * iBegin为pDataArray需要归并排序的起始位置
- * iEnd为pDataArray需要归并排序的结束位置
- *说明: 自顶向下的归并排序递归函数
- *********************************************************/
- 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); //合并前半段和后半段
- }
- }
- /********************************************************
- *函数名称:UpBottomMergeSort
- *参数说明:pDataArray 无序数组;
- * iDataNum为无序数据个数
- *说明: 自顶向下的归并排序
- *********************************************************/
- void UpBottomMergeSort(int* pDataArray, int iDataNum)
- {
- int *pTempArray = (int *)malloc(sizeof(int) * iDataNum); //临时存放合并后的序列
- RecursionMergeSort(pDataArray, pTempArray, 0, iDataNum - 1);
- free(pTempArray);
- }
- //查找数值iData在长度为iLen的pDataArray数组中的插入位置
- 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;
- }
- /********************************************************
- *函数名称:BinaryInsertSort
- *参数说明:pDataArray 无序数组;
- * iDataNum为无序数据个数
- *说明: 二分查找插入排序
- *********************************************************/
- void BinaryInsertSort(int* pDataArray, int iDataNum)
- {
- for (int i = 1; i < iDataNum; i++) //从第2个数据开始插入
- {
- 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; //插入
- }
- }
- }
- /********************************************************
- *函数名称:InsertSort
- *参数说明:pDataArray 无序数组;
- * iDataNum为无序数据个数
- *说明: 插入排序(从前向后寻找)
- *********************************************************/
- void InsertSort(int* pDataArray, int iDataNum)
- {
- for (int i = 1; i < iDataNum; i++) //从第2个数据开始插入
- {
- int j = 0;
- while (j < i && pDataArray[j] <= pDataArray[i]) //寻找插入的位置
- j++;
- if (j < i) //i位置之前,有比pDataArray[i]大的数,则进行挪动和插入
- {
- int k = i;
- int temp = pDataArray[i];
- while (k > j) //挪动位置
- {
- pDataArray[k] = pDataArray[k-1];
- k--;
- }
- pDataArray[k] = temp; //插入
- }
- }
- }
- /********************************************************
- *函数名称:InsertSort
- *参数说明:pDataArray 无序数组;
- * iDataNum为无序数据个数
- *说明: 插入排序(从后向前寻找)
- *********************************************************/
- void InsertSort1(int* pDataArray, int iDataNum)
- {
- for (int i = 1; i < iDataNum; i++) //从第2个数据开始插入
- {
- int j = i - 1;
- int temp = pDataArray[i]; //记录要插入的数据
- while (j >= 0 && pDataArray[j] > temp) //从后向前,找到比其小的数的位置
- {
- pDataArray[j+1] = pDataArray[j]; //向后挪动
- j--;
- }
- if (j != i - 1) //存在比其小的数
- pDataArray[j+1] = temp;
- }
- }
- /********************************************************
- *函数名称:SelectionSort
- *参数说明:pDataArray 无序数组;
- * iDataNum为无序数据个数
- *说明: 选择排序
- *********************************************************/
- 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++) //寻找最小的数据索引
- if (pDataArray[j] < pDataArray[index])
- index = j;
- if (index != i) //如果最小数位置变化则交换
- DataSwap(&pDataArray[index], &pDataArray[i]);
- }
- }
- /********************************************************
- *函数名称:BubbleSort
- *参数说明:pDataArray 无序数组;
- * iDataNum为无序数据个数
- *说明: 冒泡排序
- *********************************************************/
- 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()
- {
- //获取当前时间
- LARGE_INTEGER curCounter;
- QueryPerformanceCounter(&curCounter);
- return curCounter.QuadPart*1000/time_fre;
- }
- void BubbleSortTest(int *pDataArray,int length, FILE *fp)
- {
- //初始化数组
- for (int i = 0; i < length; i++)
- pDataArray[i] = rand()%100000;
- UINT64 begin;
- UINT64 end;
- begin = GetTimeM();
- BubbleSort(pDataArray, length);
- end = GetTimeM();
- fprintf(fp, " %d", int(end-begin));
- if (!CheckOrder(pDataArray, length))
- printf("BubbleSort algorithm failed!\n");
- else
- printf("BubbleSort algorithm succeed!\n");
- }
- void SelectSortTest(int *pDataArray,int length, FILE *fp)
- {
- //初始化数组
- for (int i = 0; i < length; i++)
- pDataArray[i] = rand()%100000;
- UINT64 begin;
- UINT64 end;
- begin = GetTimeM();
- SelectionSort(pDataArray, length);
- end = GetTimeM();
- fprintf(fp, " %d", int(end-begin));
- if (!CheckOrder(pDataArray, length))
- printf("SelectSort algorithm failed!\n");
- else
- printf("SelectSort algorithm succeed!\n");
- }
- void InsertSortTest(int *pDataArray,int length, FILE *fp)
- {
- //初始化数组
- for (int i = 0; i < length; i++)
- pDataArray[i] = rand()%100000;
- UINT64 begin;
- UINT64 end;
- begin = GetTimeM();
- InsertSort(pDataArray, length);
- end = GetTimeM();
- fprintf(fp, " %d", int(end-begin));
- if (!CheckOrder(pDataArray, length))
- printf("InsertSort algorithm failed!\n");
- else
- printf("InsertSort algorithm succeed!\n");
- }
- void BottomUpMergeSortTest(int *pDataArray,int length, FILE *fp)
- {
- //初始化数组
- for (int i = 0; i < length; i++)
- pDataArray[i] = rand()%100000;
- UINT64 begin;
- UINT64 end;
- begin = GetTimeM();
- BottomUpMergeSort(pDataArray, length);
- end = GetTimeM();
- fprintf(fp, " %d", int(end-begin));
- if (!CheckOrder(pDataArray, length))
- printf("BottomUpMergeSort algorithm failed!\n");
- else
- printf("BottomUpMergeSort algorithm succeed!\n");
- }
- void UpBottomMergeSortTest(int *pDataArray,int length, FILE *fp)
- {
- //初始化数组
- for (int i = 0; i < length; i++)
- pDataArray[i] = rand()%100000;
- UINT64 begin;
- UINT64 end;
- begin = GetTimeM();
- UpBottomMergeSort(pDataArray, length);
- end = GetTimeM();
- fprintf(fp, " %d", int(end-begin));
- if (!CheckOrder(pDataArray, length))
- printf("UpBottomMergeSort algorithm failed!\n");
- else
- printf("UpBottomMergeSort algorithm succeed!\n");
- }
- void QuickSortTest(int *pDataArray,int length, FILE *fp)
- {
- //初始化数组
- for (int i = 0; i < length; i++)
- pDataArray[i] = rand()%100000;
- UINT64 begin;
- UINT64 end;
- begin = GetTimeM();
- QuickSort(pDataArray, length);
- end = GetTimeM();
- fprintf(fp, " %d", int(end-begin));
- if (!CheckOrder(pDataArray, length))
- printf("QuickSort algorithm failed!\n");
- else
- printf("QuickSort algorithm succeed!\n");
- }
- void HeapSortTest(int *pDataArray,int length, FILE *fp)
- {
- //初始化数组
- for (int i = 0; i < length; i++)
- pDataArray[i] = rand()%100000;
- UINT64 begin;
- UINT64 end;
- begin = GetTimeM();
- HeapSort(pDataArray, length);
- end = GetTimeM();
- fprintf(fp, " %d", int(end-begin));
- if (!CheckOrder(pDataArray, length))
- printf("HeapSort algorithm failed!\n");
- else
- printf("HeapSort algorithm succeed!\n");
- }
- void RadixSortTest(int *pDataArray,int length, FILE *fp)
- {
- //初始化数组
- for (int i = 0; i < length; i++)
- pDataArray[i] = rand()%100000;
- UINT64 begin;
- UINT64 end;
- begin = GetTimeM();
- RadixSort(pDataArray, length);
- end = GetTimeM();
- fprintf(fp, " %d", int(end-begin));
- if (!CheckOrder(pDataArray, length))
- printf("RadixSort algorithm failed!\n");
- else
- printf("RadixSort algorithm succeed!\n");
- }
- void ShellSortTest(int *pDataArray,int length, FILE *fp)
- {
- //初始化数组
- for (int i = 0; i < length; i++)
- pDataArray[i] = rand()%100000;
- UINT64 begin;
- UINT64 end;
- begin = GetTimeM();
- ShellSort(pDataArray, length);
- end = GetTimeM();
- fprintf(fp, " %d", int(end-begin));
- if (!CheckOrder(pDataArray, length))
- printf("ShellSort algorithm failed!\n");
- else
- printf("ShellSort algorithm succeed!\n");
- }
- int main()
- {
- #define ARRAYLENGTH 10000 //无序数组初始长度
- #define ADDLENGTH 10000 //无序数组增幅
- #define MAXLENGTH 100000 //最大无序数组长度
- int length;
- srand(time(NULL));
- //获取时钟频率
- LARGE_INTEGER litmp;
- QueryPerformanceFrequency(&litmp);
- time_fre = (UINT64 )litmp.QuadPart;
- int *pDataArray = new int[MAXLENGTH];
- FILE *fp = fopen("data.txt", "w"); //将结果存储与data.txt文件中;
- //每一行代表一种排序在不同数据规模下的时间(毫秒)
- length = ARRAYLENGTH;
- for (; length <= MAXLENGTH; length += ADDLENGTH)
- {
- BubbleSortTest(pDataArray, length, fp);
- }
- fprintf(fp, "\n");
- length = ARRAYLENGTH;
- for (; length <= MAXLENGTH; length += ADDLENGTH)
- {
- SelectSortTest(pDataArray, length, fp);
- }
- fprintf(fp, "\n");
- length = ARRAYLENGTH;
- for (; length <= MAXLENGTH; length += ADDLENGTH)
- {
- InsertSortTest(pDataArray, length, fp);
- }
- fprintf(fp, "\n");
- length = ARRAYLENGTH;
- for (; length <= MAXLENGTH; length += ADDLENGTH)
- {
- BottomUpMergeSortTest(pDataArray, length, fp);
- }
- fprintf(fp, "\n");
- length = ARRAYLENGTH;
- for (; length <= MAXLENGTH; length += ADDLENGTH)
- {
- UpBottomMergeSortTest(pDataArray, length, fp);
- }
- fprintf(fp, "\n");
- length = ARRAYLENGTH;
- for (; length <= MAXLENGTH; length += ADDLENGTH)
- {
- QuickSortTest(pDataArray, length, fp);
- }
- fprintf(fp, "\n");
- length = ARRAYLENGTH;
- for (; length <= MAXLENGTH; length += ADDLENGTH)
- {
- HeapSortTest(pDataArray, length, fp);
- }
- fprintf(fp, "\n");
- length = ARRAYLENGTH;
- for (; length <= MAXLENGTH; length += ADDLENGTH)
- {
- RadixSortTest(pDataArray, length, fp);
- }
- fprintf(fp, "\n");
- length = ARRAYLENGTH;
- for (; length <= MAXLENGTH; length += ADDLENGTH)
- {
- ShellSortTest(pDataArray, length, fp);
- }
- fprintf(fp, "\n");
- fclose(fp);
- free(pDataArray);
- return 0;
- }
相关文章
- 12-21选择排序
- 12-21闲着没事做,用js做了一个冒泡排序的动画
- 12-21冒泡排序
- 12-21学习笔记-插入排序
- 12-21插入排序(附图)
- 12-21插入排序
- 12-21八大排序(三)之插入排序
- 12-2113.插入排序--直接插入排序(简单插入排序)
- 12-21CF1131D Gourmet choice(并查集,拓扑排序)
- 12-21图论-拓扑排序-应用