数据结构-排序问题

?? 排序分为以下几大类：a:插入排序；b:选择排序；c:交换排序；d:归并排序；e:基数排序。

? a:插入排序:分为直接插入排序与希尔排序。直接插入排序的思想是：每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。第一趟比较前两个数,然后把第二个数按大小插入到有序表中; 第二趟把第三个数据与前两个数从前向后扫描，把第三个数按大小插入到有序表中；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。直接插入排序属于稳定的排序，时间复杂性为o(n^2)，空间复杂度为O(1)。

poj 2388代码：

#include <iostream>using namespace std;const int Max=10002;void QuickSort(int a[],int low,int high){int i,j;if(low>high)return;i=low;j=high;int temp;temp=a[i];while (i<j){while(i<j&&temp<a[j])j--;if (i<j){a[i]=a[j];i++;}while(i<j&&a[i]<temp)i++;if(i<j){a[j]=a[i];j--;}}a[i]=temp;QuickSort(a,low,--j);QuickSort(a,++i,high);}int main(){int n;int b[Max];cin>>n;for (int k=0;k<n;k++)cin>>b[k];QuickSort(b,0,n-1);cout<<b[n/2]<<endl;return 0;}

?

?关于归并排序，以后再进行详细解释！！

?

?

?

?