100万个无序数排序算法的运行时间比较-365bet是什么公司-365bet规则-365bet线上娱乐-365bet是什么公司

冒泡排序（时间复杂度N2，空间复杂度1）

依次比较数组相邻两个元素，将最大或最小元素放到后面，慢慢“浮”到数列的最后。选择排序（时间复杂度N2，空间复杂度1）

首先找到数组最小元素，将它和数组的第一个元素交换位置。再次，在剩下的元素中找到最小的元素，将它与数组第二个元素交换，如此往复。插入排序（时间复杂度介于N和N2之间，空间复杂度1）将数组分为有序和无序两个部分，默认数组左变第一个元素是有序的，依次遍历数组第二个元素到最后，与数组左变有序序列比较。如果小于左变有序序列则交换位置。希尔排序（时间复杂度NlogN，空间复杂度1）

分组+插入排序。插入排序只能交换相邻的元素，元素只能一点一点从数组的一端移动到另一端。希尔排序的思想是使数组中任意间隔为gap的数组都是有序的。经验公式：gap=gap/3+1，如果有12个元素，那么同一组元素相邻元素间隔4，下一次分组间隔2，最后一次间隔1。归并排序（时间复杂度NlogN,空间复杂度N（递归临时变量））

将两个有序数组归并到第三个数组中，递归在发生在处理数组之后。快速排序（时间复杂度NlogN，空间复杂度lgN））

与归并一样，都是利用分治的排序算法。将数组分成两个子数组，将两部分独立排序，递归发生在处理数组之前。不需要额外的内存空间存储一个临时数组。堆排序（时间复杂度NlogN，空间复杂度1）

利用堆（一种特殊的完全二叉树）而设计的一种排序算法。如果是正序排序，先构建一个最大堆，交换a[1]和a[n]，此时a[n]就是数组中最大元素。n–,a[1]向下调整保持最大堆特性，进行下一次交换。桶排序（时间复杂度lg(M+N)，空间复杂度N）

构建一个临时数组book，长度为要排序数组的最大值。遍历一次数组a,记录a[i]的值的次数：book[a[i]]++j.最后遍历一遍数组book，将i值和出现的数次写到数组a中。

这里是引用

#include

using namespace std;

//效率测试

#define NUMBER 1000000

long long getSystemTime()

{

struct timeb t;

ftime(&t);

return 1000 * t.time + t.millitm;

}

void bucketSort(int *a,int *book, int len)

{

for (int i = 0; i < len; i++)

{

int tem = a[i];

book[tem]++;

}

int k = 0;

for (int i = 0; i < NUMBER; i++)

{

int ncount = book[i];

for (int j = 0; j < ncount; j++)

{

a[k++] = i;

}

//-----------------三向切分的快速排序 ---------------------

void quick3WaySort(int *a, int left, int right)

{

if (left > right) return;

int lt = left;

int i = left + 1;

int gt = right;

int tem = a[left];

while (i <= gt)

{

if (a[i] < tem) //小于切分元素的放在lt左边，lt和i整体右移

{

//exchange(a, lt++, i++);

int tmp = a[i];

a[i] = a[lt];

a[lt] = tmp;

lt++; i++;

}

else if (a[i] > tem)//大于切分元素的放在gt右边，因此gt左移

{

//exchange(a, i, gt--);

int tmp = a[i];

a[i] = a[gt];

a[gt] = tmp;

gt--;

}

else

i++;

}

quick3WaySort(a,left,lt-1);

quick3WaySort(a, gt+1, right);

}

#if 0

void quickSort(int *a, int left, int right)

{

if (left > right) return;

int i = left;

int j = right;

int tem = a[left];

while (i != j)

{

while (a[j]>tem && i

j--;

while (a[i] <= tem &&i

i++;

if (i < j)

{

int t = a[j];

a[j] = a[i];

a[i] = t;

}

a[left] = a[i];

a[i] = tem;

quickSort(a, left, i - 1);

quickSort(a, i+1, right);

return;

}

#endif

//---------------堆排序--------------------

void shiftDown(int *a,int len,int i)

{

int index, flag = 0;

//----结点有左孩子-----

while (i * 2 <= len && flag == 0)

{

if (a[i] < a[i * 2])

index = i * 2;

else

index = i;

//----结点有左孩子-----

if (i * 2 + 1 <= len)

{

if (a[index] < a[i * 2 + 1])

index = i * 2 + 1;

}

if (index != i)

{

//---交换i节点与子节点，更新编号为下一次向下调整准备

int tem = a[i];

a[i] = a[index];

a[index] = tem;

i = index;

}

else

{

flag = 1;

}

void heapSort(int *a, int len)

{

//-------------建最大堆----------------

for (int i = len / 2; i >= 1; i--)

{

shiftDown(a,len,i);

}

//--------------排序-------------------

while (len>1)

{

int tem = a[len];

a[len] = a[1];

a[1] = tem;

len--;

shiftDown(a,len,1);

}

//-------------------归并排序-------------------------

void merge(int *a, int first, int mid, int last, int *temp)

{

int i = first; // 第1个有序序列的开始下标

int j = mid + 1; // 第2个有序序列的开始下标

int len = 0;

// 合并两个有序序列

while (i <= mid && j <= last)

{

if (a[i] < a[j])

{

// 找二者中比较小的数

temp[len] = a[i];

i++;

}

else

{

temp[len] = a[j];

j++;

}

len++;

}

while (i <= mid)

{

temp[len] = a[i];

i++;

len++;

}

while (j <= last)

{

temp[len] = a[j];

j++;

len++;

}

// 找到原来的第一个有序序列的开始位置覆盖无序序列

for (int k = 0; k < len; k++)

{

a[first+k] = temp[k];

}

void mergeSort(int *a, int first, int last, int *temp)

{

if (first == last)

return;

int mid = first+ (last - first) / 2; //防止first+last溢出

mergeSort(a, first, mid, temp);

mergeSort(a, mid+1, last, temp);

merge(a, first, mid, last, temp);

}

//-------------------希尔排序-------------------

void shellSort(int *a, int len)

{

int gap = len;

int index, tem;

while (gap > 1)

{

gap = gap / 3 + 1;

// =======分组, 对每一组, 进行插入排序

for (int i = 0; i < gap; i++)

{

//----插入排序----------

for (int j = i + gap; j < len; j += gap)

{

index=j;

tem=a[j];

for (int k = j; k > i; k -= gap)

{

if (tem < a[k - gap])

{

a[k] = a[k - gap];

index = k - gap;

}

else

{

break;

}

a[index] = tem;

}

//--------------------插入排序---------------------

void insertSort(int *a, int len)

{

int index;

int tem;

// 遍历无序序列

for (int i = 1; i < len; i++)

{

index = i; //存储当前基准数位置

tem = a[i];

// 遍历有序序列

for (int j = i; j >0; j--)

{

if (tem < a[j - 1]) //找到比基准数大的位置，则将有序序列后移，并记录有序序列位置

{

a[j] = a[j - 1];

index = j - 1;

}

else

{

break;

}

a[index] = tem; //将基准数填入

}

//--------------选择排序---------------

void selectSort(int *a, int len)

{

for (int i = 0; i < len; i++)

{

int min = i;//基准书位置

for (int j = i + 1; j < len; j++)

{

if (a[min] > a[j])

min = j; //没遍历一次，找到最小值的序号

}

int tem = a[min]; //交换基准数和最小元素

a[min] = a[i];

a[i] = tem;

}

//----------------冒泡排序------------------

void bubbleSort(int *a, int len)

{

int flag = 0;//0表示没有排序好，1表示排序好了

for (int i = 0; i < len && flag == 0; i++)

{

//每进行一次冒泡，首先默认已经排好

flag = 1;

for (int j = 1; j < len - i; j++)

{

if (a[j] < a[j - 1])

{

int tem = a[j - 1];

a[j - 1] = a[j];

a[j] = tem;

flag = 0;

}

int main()

{

long long timeStart, timeEnd, timeUse;

srand((unsigned)time(NULL));

int(*array)[NUMBER] = new int[7][NUMBER];

int *arrayHeap = new int[NUMBER+1];

//-----归并和桶排序额外的内存---

int *mergeArray = new int[NUMBER];

int *bucketArrayBook = new int[NUMBER]();

for (int i = 0; i < NUMBER; ++i)

{

//生成一个小于len的随机数

int number = rand() % NUMBER;

for (int j = 0; j < 7; ++j)

{

array[j][i] = number;

}

arrayHeap[i+1] = number;

}

cout << "对第" << NUMBER << "个数进行排序" << endl;

timeStart = getSystemTime();

bucketSort(array[0], bucketArrayBook, NUMBER);

timeEnd = getSystemTime();