排序算法（一） -电脑资料

    进入找工作倒计时状态了，计划好好复习一下数据结构和相关算法，预计用两天时间把见过的排序算法整理下，首先看一下时间复杂度为O（n2）的算法，

排序算法（一）

    首先参考大话数据结构定义一个链表类：

#include#define MAXSIZE 1000 using namespace std; class SqList{ public: SqList():length(0){} SqList(int length1,int value=0):length(length1) { for(int i=0;i=MAXSIZE) { return false; } data[length]=value; length++; } friend ostream& operator<<(ostream& output, SqList list); public: int data[MAXSIZE]; int length; }; void swap(int& a,int &b) { int tmp=a; a=b; b=tmp; } ostream& operator<<(ostream& output, SqList list) { for (int i = 0; i
    冒泡排序法：
/** *冒泡排序即相邻的两者相互比较，根据需求把较大的或较小的前移或后移 *记住，两两相邻的比较是冒泡排序的特点之一 */void BubbleSort1(SqList* list){//每次遍历时把较大者后移	int length=list->length;	while(length>0)	{		for(int i=0;i<length-1;++i) list-="">data[i] > list->data[i+1])				swap(list->data[i],list->data[i+1]);		}		length--;	}}void BubbleSort2(SqList* list){//每次遍历时，把较小的前移	for(int i=0;i<li>length;i++)	{		for(int j=list->length-2;j>=i;j--)		{			if(list->data[j] > list->data[j+1])				swap(list->data[j],list->data[j+1]);		}	}	}</list-></length-1;++i)>
    选择排序法：
/** *选取排序即每次在未排序队列当中选取一个最小值，然后与第i个值进行交换，直至i为length为止； *当然，也可以选取最大值把到后面，根据需求而定 */void selectSort(SqList* list){	for (int i = 0; i < list->length; ++i)	{		int min = list->data[i];		int pos = i;		for (int j = i+1; j < list->length; ++j)		{			if (list->data[j] < min)			{				min = list->data[j];				pos = j;			}		}		if (pos != i)		{			swap(list->data[i], list->data[pos]);		}	}}
    简单插入排序法：
<span>/** *遍历链表，把每个元素插入到正确位置 */void InsertSort1(SqList *list){	for (int i = 1; i < list->length; ++i)	{		int j = i - 1;		for (; j >=0; j--)		{			if (list->data[i] > list->data[j])				break;		}		int tmp = list->data[i];		for (int k = i; k > j+1; --k)		{			list->data[k] = list->data[k - 1];		}		list->data[j + 1] = tmp;	}}void InsertSort2(SqList *list){	for (int i = 1; i < list->length; ++i)	{		if (list->data[i] < list->data[i - 1])		{			int tmp = list->data[i];			int j = i-1;			for (; j >= 0 && list->data[j] > tmp; --j)			{//查找的同时，进行后移操作				list->data[j + 1] = list->data[j];			}			list->data[j + 1] = tmp;		}	}}</span>
    希尔排序法（简单插入排序的改进）：
/** *希尔排序是插入排序的一种改进，可以理解为把一个数组分成几个小的数组进行插入排序，再合并使原数组基本有序，
电脑资料
《排序算法（一）》(http://meiwen.anslib.com)。 *希尔排序一个很关键的步骤是增量的选取，合适的增量能够提高排序效率，但不合适的增量可能会导致程序崩溃或结果错误。 *其次，希尔排序也不是一个稳定的排序算法，因为它是跳跃插入排序的。 *希尔排序只是比前面几种O(n2)的效果稍好，并不会优于后面要提到的快速排序等算法。 */void ShellSort(SqList* list){	int increment = list->length;	do{		increment = increment / 3 + 1;		for (int i = increment + 1; i < list->length; ++i)		{			if (list->data[i] < list->data[i - increment])			{				int tmp = list->data[i];				int j = i - increment;				for (; j >= 0 && list->data[j] > tmp; j -= increment)				{					list->data[j + increment] = list->data[j];				}				list->data[j + increment] = tmp;			}		}	} while (increment > 1);}