数据结构八大排序对比总结

针对前面讨论的八大经典排序算法：冒泡排序、插入排序、选择排序、堆排序、归并排序、快速排序、希尔排序、桶排序。

关于各种什么时间复杂度，空间复杂度的对比总结，网上一大堆，别人也总结的很好，这里就不赘述了，这里主要通过对大量数据进行排序测试，测试各排序算法的运行时间，来比较各排序之间优劣（时间上）。

先贴出测试程序：最后会给出各数据量的情况下，各算法的运行时间。

typedef void(*SortFun)(int Arr[], int length);  //函数指针

double SortTest(SortFun fp)
{
	int Arr[LENGTH];
	for (int i = 0; i < LENGTH; ++i)
		Arr[i] = rand() % MAXNUM;
	clock_t beginTime = clock();
	fp(Arr, LENGTH);
	double diffTime = double(clock() - beginTime) / CLOCKS_PER_SEC;

	return diffTime;

}

上面的 LENGTH 和 MAXNUM 宏定义在另外一个头文件中（因为桶排序中需要用到 MAXNUM），LENGTH 为待排数据的量，MAXNUM 为待排数据数值的最大值。
为了方便调用函数指针，这里在原排序程序的基础上添加了一个通用的函数接口。为方便理解，这里重新贴出各排序程序

1、选择排序

思想：每次找一个最小值

特点：不稳定排序，in-place sort

最坏时间情况：O(N^2)

最好时间情况：O(N^2)

空间复杂度：O(1)

void SelectSort(int Array[], int length)
{
	int i, j;
	int Minindex;

	for (i = 0; i < length - 1; ++i)    //最后留下的元素自然是最大的
	{
		Minindex = i;
		for (j = i + 1; j < length; ++j)
		{
			if (Array[j] < Array[Minindex])
				Minindex = j;         //更新最小值的索引
		}
		swap(Array[i], Array[Minindex]);   //将最小值与无序区的第一个元素交换
	}

}

2、桶排序

思想：类似于哈希表的分离链表法，定义一个映射函数，将关键字划入对应的桶中

特点：稳定排序

最坏时间情况：全部分到一个桶中O(N^2)，一般情况为O(NlogN)

最好时间情况：每个桶中只有一个数据时最优O(N)

空间复杂度：典型地以空间换时间，和哈希表类似，看要多少桶

typedef struct Node
{
	int data;
	struct Node *next;
}node;

void AddtoBucket(node *&pNode, int value)
{
	node *pHead = NULL;
	int tempValue;

	node *pNew = new node;
	pNew->data = value;
	pNew->next = NULL;
	 
	if (NULL == pNode)
	{
		pNode = pNew;
	}
	else
	{
		pHead = pNode;
		while ((pNode->data <= value) && (pNode->next != NULL))
			pNode = pNode->next;
	 
		if (pNode->data <= value)
		{
			pNode->next = pNew;
		}
		else
		{
			//插入链表，这里采用的是修改值的方法，即插入指定节点的前面，无需获得该节点的前一节点  
			//只需修改该节点的值使其等于待插入节点值，然后该节点指向新建节点，新建节点的键值则设为前面节点的键值  
			tempValue = pNode->data;
			pNode->data = pNew->data;
			pNew->data = tempValue;
			//修改指针
			pNew->next = pNode->next;
			pNode->next = pNew;
		}
		pNode = pHead;  //修正头节点指针
	}

}

void BucketSort(int Arr[], int length, int MaxNum)
{
	node **list = new node*[length];   //分配指针数组空间
	for (int i = 0; i < length; ++i)
		list[i] = NULL;

	int index;
	 
	for (int i = 0; i < length; ++i)
	{
		index = (Arr[i] * length) / (MaxNum + 1);  //映射函数，可自定义
		AddtoBucket(list[index], Arr[i]);
	}
	 
	//将桶中的数据放入原来的串行中
	for (int i = 0, j = 0; i < length; ++i)
	{
		while (list[i] != NULL)
		{
			Arr[j++] = list[i]->data;
			list[i] = list[i]->next;
		}
	}
	//销毁分配的空间，code 略

}

//统一接口
void BucketSortTest(int Arr[], int length)
{
	BucketSort(Arr, length, MAXNUM);
}
3、

希尔排序

思想：分割成子序列，然后用直接插入排序

特点：不稳定排序算法

平均时间复杂度：O()

空间复杂度：O(1)

void ShellSort(int Array[], int length)
{
	int i, j, gap;
	int temp;

	for (gap = length / 2; gap > 0; gap /= 2)
	for (i = 0; i < gap; ++i)
	{
		//下面为直接插入排序，排序的是数组里间隔gap的元素
		for (j = i + gap; j < length; j += gap)
		{
			int k = j - gap;
			temp = Array[j];
			while (k >= 0 && Array[k] > temp)
			{
				Array[k + gap] = Array[k];
				k -= gap;
			}
			Array[k + gap] = temp;
		}
	}

}

4、插入排序

思想：将无序区的元素比较插入到有序区适当位置，是移动不是交换，所以是稳定排序算法

特点：稳定排序算法，in-place sort

时间复杂度：最坏O(N^2)，最优O(N)

void InsertSort(int Array[], int length)
{
	int i, j;
	int temp;

	for (i = 1; i < length; ++i)
	{
		j = i - 1;
		temp = Array[i];          //待插入数据，即无序区的第一个元素
	 
		while ((j >= 0) && (temp < Array[j]))  //跳出循环的两个条件
		{
			Array[j + 1] = Array[j];    //数据后移
			--j;
		}
		Array[j + 1] = temp;
	}

}

5、归并排序

思想：分治法

特点：稳定排序算法

时间复杂度：O(NlogN)

空间复杂度：O(N+logN)

void Merge(int unsorted[], int first, int mid, int last, int sorted[])
{
	int i = first, j = mid;
	int k = 0;

	while (i < mid && j < last)
	{
		if (unsorted[i] < unsorted[j])
			sorted[k++] = unsorted[i++];
		else
			sorted[k++] = unsorted[j++];
	}
	 
	while (i < mid)
		sorted[k++] = unsorted[i++];
	 
	while (j < last)
		sorted[k++] = unsorted[j++];
	 
	/*2-路合并的结果，与后面一路是无序的(这两路不在同一序列中)，
	需要将前面合并的结果导入输入序列中，再次进行2-路合并,first表征相对位置*/
	for (int v = 0; v < k; ++v)
		unsorted[v + first] = sorted[v];

}

/*分割及归并排序*/
void MergeSort(int unsorted[], int first, int last, int sorted[])
{
	if (first + 1 < last)
	{
		int mid = first + ((last - first) >> 1); //mid=(left+right)>>1;当left和right比较大时，有溢出的危险
		MergeSort(unsorted, first, mid, sorted);
		MergeSort(unsorted, mid, last, sorted);
		Merge(unsorted, first, mid, last, sorted);
	}
}

//统一接口
void MergeSortTest(int Arr[], int length)
{
	int *sorted = new int[length];
	MergeSort(Arr, 0, length, sorted);
}
6、

堆排序

思想：最大堆（最小堆）

特点：不稳定排序算法

时间复杂度：O(NlogN)

空间复杂度：O(1)

#define PARENT(x) ((x-1) >> 1)

#define LEFT(x)   ((x << 1) + 1)

#define RIGHT(x)  ((x << 1) + 2)


//调整最大堆
void MaxHeapify(int Array[], int Index, int HeapSize)
{
	int L = LEFT(Index);   //Index为父节点索引
	int R = RIGHT(Index);
	int Largest;

	//选择三（两个）个元素（“血缘关系”）的最大值
	if (L <= HeapSize && Array[L] > Array[Index])
		Largest = L;
	else
		Largest = Index;
	 
	if (R <= HeapSize && Array[R] > Array[Largest])
		Largest = R;
	 
	if (Largest != Index)
	{
		swap(Array[Largest], Array[Index]);  //最大值与父节点位置交换
		MaxHeapify(Array, Largest, HeapSize);
		/*这里的MaxHeapify()递归是用于最大堆的调整，从上至下调整，且只需调整一棵子树
		构建最大堆是从数组尾端往前，并不需要递归，实际上构建时也不会出现递归调用*/
	}

}

//构建最大堆
void BuildHeapify(int Array[], int HeapSize)
{
	for (int i = PARENT(HeapSize); i >= 0; --i)
		MaxHeapify(Array, i, HeapSize);       //必须单步向前
}

void HeapSort(int Array[], int length)
{
	int HeapSize = length - 1;

	BuildHeapify(Array, HeapSize);
	 
	for (int i = HeapSize; i >= 0; --i)
	{
		swap(Array[0], Array[i]);
		--HeapSize;
		MaxHeapify(Array, 0, HeapSize);
		//删除根节点后，，有一棵子树满足最大堆，有一棵不满足，只需调整一棵子树
	}

}

7、快速排序

思想：分治，化整为零，与基准比较

特点：不稳定排序算法

时间复杂度：O(NlogN)，如果数据本来是排序好的，最坏O(N^2)

空间复杂度：O(logN)

int Partition(int Array[], int left, int right)
{
	int L = left, R = right;
	int pivot = Array[L];

	while (L < R)
	{
		while ((L < R) && (Array[R] > pivot))
			--R;
		if (L < R)
		{
			Array[L] = Array[R];   //补数的时候，要知道空位在哪
			++L;
		}
	 
		while ((L < R) && (Array[L] < pivot))
			++L;
		if (L < R)
		{
			Array[R] = Array[L];
			--R;
		}
	}
	 
	Array[L] = pivot;    //补上最后的空位
	return L;

}

void QuickSort(int Array[], int left, int right)
{
	if (left < right)
	{
		int pos = Partition(Array, left, right);
		QuickSort(Array, left, pos - 1);           //注意边界
		QuickSort(Array, pos + 1, right);
	}
}

//统一接口
void QuickSortTest(int Arr[], int length)
{
	QuickSort(Arr, 0, length - 1);
}

8、冒泡排序

思想：冒泡

特点：稳定排序算法

时间复杂度：O(N^2)

void BubbleSort(int Array[], int length)
{
	for (int i = 0; i < length - 1; ++i)
	for (int j = 1; j < length - i; ++j)    //单次之后最大数据在最后面  
	{
		if (Array[j - 1] > Array[j])
			swap(Array[j - 1], Array[j]);
	}
}

主程序：
避免长久的等待，将冒泡排序置最后。

int main()
{
	cout << "BucketSort:  " << SortTest(BucketSortTest) << endl;
	cout << "HeapSort  :  " << SortTest(HeapSort) << endl;
	cout << "InsertSort:  " << SortTest(InsertSort) << endl;
	cout << "MergeSort :  " << SortTest(MergeSortTest) << endl;
	cout << "QuickSort :  " << SortTest(QuickSortTest) << endl;
	cout << "SelectSort:  " << SortTest(SelectSort) << endl;
	cout << "ShellSort :  " << SortTest(ShellSort) << endl;
	cout << "BubbleSort:  " << SortTest(BubbleSort) << endl;

	return 0;

}

结果：

#define LENGTH 20000   //数据量

#define MAXNUM 10000   //数据的最大值

#define LENGTH 10000   //数据量

#define MAXNUM 10000   //数据的最大值

#define LENGTH 5000   //数据量

#define MAXNUM 10000   //数据的最大值

#define LENGTH 50000   //数据量

#define MAXNUM 100000   //数据的最大值

这里的冒泡排序需要等很久

上面运行时间的计算，受很多因素的影响，这里只是对比各大排序的排序时间。毫无疑问快速排序是最快的。