排序小结

排序算法是基础之基础。在这里小结一下。方便自己查阅和学习。

1.冒泡排序(BubbleSort)

思想：比较相邻的两个元素，如果前面的元素大于后面的元素，交换之。

思路：采用双层循环。外循环控制要处理多少趟。里面循环用来做元素的交换操作。注意上下界。

稳定性：稳定

时间复杂度：O(n2)

voidbubbleSort(inta[],intsize){inttmp;for(inti=0;i<size;i++){//每一趟都会把最大的元素放入最右边的位置//最右边的位置会一点点往左移动for(intj=0;j<size-i-1;j++){if(a[j]>a[j+1]){tmp=a[j];a[j]=a[j+1];a[j+1]=tmp;}}}}


2.快速排序(quickSort)

思想：找到第一个元素的最终位置，然后对数组进行分割，对左边的进行快排，对右边的进行快排。

思路：采用递归，需要一个辅助函数findPos()来找到某一个元素的最终位置。

稳定性：不稳定

时间复杂度：有时O(nlogn),最坏情况是已经排好序，这样时间复杂度为O(n2)

伪算法

/*

*快速排序（伪算法） 2016-08-14 11:01:34

* 1.先找到第一个元素的最终位置

* 2.对第一个元素的最终位置之前的元素，进行快速排序。

* 3.对第一个元素的最终位置之后的元素，进行快速排序。

*

*/

intfindPos(inta[],intlow,inthigh){intval=a[low];while(low<high){//因为val取的是最前面的值，所以先从后往前遍历比较while(low<high&&a[high]>=val)high--;a[low]=a[high];//将后面较小值赋值给前面已经做好备份的位置上//然后从前往后遍历比较while(low<high&&a[low]<=val)low++;a[high]=a[low];//将前面较大值赋值给后面已经做好备份的位置上}a[low]=val;returnlow;}voidquickSort(inta[],intlow,inthigh){if(low<high){intpos=findPos(a,low,high);quickSort(a,low,pos-1);quickSort(a,pos+1,high);}}


3.直接插入排序(insertSort)也叫选择插入排序

思想：将第i个元素插入到前面i-1个已排好序的记录中。直到所有的元素都排一次。

思路：见伪算法

稳定性：稳定

时间复杂度：O(n2)

伪算法

/*

*插入排序（伪算法） 2016-08-14 12:23:09

* 1. 将相邻的两个元素比较，如果前面的数大于后面的数，则交换。

* 直到找到前面的数小于后面的，就把这个值插入到这个位置。

* 2. 循环1，直到所有的元素都有序排列。

*

*/

voidinsertSort(inta[],intsize){inti,j,tmp;for(i=0;i<size;i++){tmp=a[i];for(j=i-1;j>=0&&a[j]>tmp;j--){a[j+1]=a[j];}a[j+1]=tmp;}}


4.选择排序(selectSort)

思想：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在待序列的起始位置。

思路：见伪算法

稳定性：不稳定

时间复杂度：O(n2)

伪算法

/*

*选择排序（伪算法） 2016-08-14 13:08:50

* 1. 工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在待序列的起始位置。

* 2. 循环1，直到全部待排序的数据元素排完。

*

*/

voidselectSort(inta[],intsize){intcurrentSmallIndex;//记录待排序队列中最小元素的下标inttmp;//记录最小元素的大小for(inti=0;i<size;i++){tmp=a[i];currentSmallIndex=i;for(intj=i+1;j<size;j++){if(a[j]<tmp){currentSmallIndex=j;tmp=a[j];}}a[currentSmallIndex]=a[i];a[i]=tmp;}}


5.归并排序(mergeSort)

思想：将数组递归分成2半，知道数组的长度为1，然后将分成2半的数组合并。

思路：需要使用辅助函数merge()来合并

稳定性：稳定

时间复杂度：O(n2)

伪算法

/*

1.将数组分成左右两半

2.递归1，直道只剩1个元素的时候，然后合并。

*/

voidmerge(inta[],intstart,intend){intmid=(start+end)/2;intleft,right;int*temp=newint[end-start+1];intk=0;//临时数组的下标left=start;right=mid+1;while(left<=mid&&right<=end){while((left<=mid&&right<=end)&&(a[left]<a[right]))temp[k++]=a[left++];while((left<=mid&&right<=end)&&(a[right]<a[left]))temp[k++]=a[right++];}while(left<=mid)temp[k++]=a[left++];while(right<=end)temp[k++]=a[right++];//将临时数组中的元素，找到原数组的位置，按位赋值过去。//这里需要注意原数组的起始位置是start，而不是0for(inti=start,k=0;i<=end;i++,k++)a[i]=temp[k];delete[]temp;}voidmergeSort(inta[],intstart,intend){if(start<end){intmid=(start+end)/2;mergeSort(a,start,mid);//左数组合并排序mergeSort(a,mid+1,end);//右数组合并排序merge(a,start,end);//整体排序}}


排序总结未完待续。

2016-08-14 16:11:27