排序
插入排序
1、直接插入排序
基本思想：每次将一个待排序的记录插入到已经排好序的记录数据区中，直至全部插入为止。
算法思路：将r[0...n-1]中的数据从小到大排序
- 令i=0,j=i+1,r[0...i]为有序区，r[i+1...n]为待排序区
- while：j<n
- 将r[j]插入到r[0...i]中
- t=r[j] t为待排序区中第一个数据 为基准点
- while(j>=1)
- if t<r[j-1] 基准点小于排序区的数 r[j]=r[j-1] j--
- else 跳出内层循环、
- 此时 j 的位置就是刚待排序区 基准点数的值
- i++,j=i+1
- return
代码
for(i=0;i<tab->len-1;i++)
{
Data* t=tab->data[i+1];
for(j=i+1;j>=1;j--){
if(t->num<tab->data[j-1]->num){
tab->data[j]=tab->data[j-1];
moveCounts+=3;
compareCounts++;
}else
break;
}
compareCounts++;
tab->data[j]=t;
}
复杂度
最好情况元素有序，复杂度O(n),最坏情况逆序，时间复杂度O(n2),平均时间复杂度O(n2)
空间复杂度O(1) 稳定
2、希尔排序
缩小增量排序：
- step1：设置初始增量k=d(i)=n/2
- step2:按照增量k，把全部记录从第一个记录开始分组，所有相距k的为一组，组内进行插入排序
- step3：取新的增量k=d(i+1),d(i+1)=d(i)/2 直到d(i)=1 k==1 转step4 否则转step2
- return
代码
while(d>0){
for(n=d;n<tab->len;n++)
{
Data* tmp=tab->data[n];
for(j=n;j>=d;j=j-d)//组内直接插入排序
{
compareCounts++;
if(tmp->num<tab->data[j-d]->num){
tab->data[j]=tab->data[j-d];
moveCounts+=3;
}
else
break;
}
tab->data[j]=tmp;
}
d=d/2;
}
int tmp = 0,j;
for(int i = gap;i < array.length;i++){
tmp = array[i];
for(j = i-gap;j >= 0;j = j-gap){
if(array[j] > tmp){
array[j+gap] = array[j];
}else{
break;
}
}
array[j+gap] = tmp;
}
复杂度：最好O（n1.3），最坏O(n2),不稳定 平均O(nlogn)
交换排序：
3、冒泡排序
- 将第一个关键字与第二个关键字进行比较，若逆序，交换
- 比较第二个和第三个记录
- 依次比较直到n-1和n个记录
- 关键字最大的记录被安排在最后一个位置
- 对前n-1个记录进行第二趟排序
代码
for(i=0;i<tab->len-1;i++){
for(j=0;j<tab->len-1-i;j++)
{
if(tab->data[j]->num>tab->data[j+1]->num)
{
Data* tmp=tab->data[j];
tab->data[j]=tab->data[j+1];
tab->data[j+1]=tmp;
}
}
}
时间复杂度：最好O(n),最坏O(n2),平均O(n2)
空间复杂度：O(1),稳定
4、快速排序
基本思想：对一组无序的集合，选择任意元素作为它的基点，该基点左边的元素都小于或等于它，基点的右边元素都大于等于它。根据基点分为左右半区，对左右半区进行快速排序。
代码
int searchPoint(L* tab,int low,int high)
{
int i=low;
int j=high;
Data* t=tab->data[i];
while(i<j){
while(t->num<=tab->data[j]->num&&i<j)//在右边找比基准点小的数进行交换
j--;
if(i<j){
tab->data[i]=tab->data[j];//比基准点小的放在基准点左边
i++;
}
while(t->num>tab->data[i]->num&&i<j)//在左边找比基准点大的进行交换
i++;
if(i<j){
tab->data[j]=tab->data[i];//比基准点大的放在基准点右边
j--;
}
}
tab->data[i]=t;//基准点
return i;
}
void quickSort(L* tab,int low,int high){
if(low<high){
int pos=searchPoint(tab,low,high);
quickSort(tab,low,pos-1);//左半区
quickSort(tab,pos+1,high);//右半区
}
}
最好情况
每次取的基准都是无序区的中值，划分结果两个无序区的长度相等。
最坏情况
每次划分的基准都是无序区中关键字最小或者最大的元素，划分的结果是基准点得左边或者右边为空，划分前后无序区的元素只减少了一个，因此排序要做n-1躺，
时间复杂度:最佳O(nlogn),平均O(nlogn),最坏O(n^2)
空间复杂度：最佳:递归调用使用栈空间O(logn)+1,最坏情况需要O(n^2)
不稳定
选择排序
5、简单选择排序
基本思想：
每次从待排序区中选择一个关键值最大或者最小的记录放在已排序列中直到全部排完。
- step1：通过n-1次比较，在n个记录中，找出关键字最小的记录，将它与第一个记录交换。
- step2：通过n-2次比较在n-1个记录中，找出关键值最小的记录，将它与第二个记录交换
- 重复操作直到完成n-1趟排序
代码
for(i=0;i<tab->len;i++){
k=i;
min=tab->data[k]->num;
for(j=i;j<tab->len;j++){
if(min>tab->data[j]->num){
k=j;
min=tab->data[j]->num;
}
}
if(k!=i)//{
Data* tmp=tab->data[i];
tab->data[i]=tab->data[k];
tab->data[k]=tmp;
}
}
时间复杂度：最佳最坏平均都是O(n^2)
空间复杂度O(1) 不稳定
6、堆排序
大根堆：根结点（堆顶）是堆里所有节点关键字最大的
小根堆：根结点是堆里所有节点关键字最小的
Ki<=K2i&&Ki<=K2i+1或者Ki>=K2i&&Ki>=K2i+1
基本思想：将待排序序列构造成为一个大根堆，将大根堆的堆顶也就是最大元素与数组末尾元素进行交换，这样最大元素就沉到数组末尾。剩下的n-1个元素继续构造大根堆，将堆顶与数组倒数第二个元素进行交换。如此反复
-
将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;
-
将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;
-
重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。
代码
void adjustHeap(L* tab,int index,int bound)//构建大根堆
{
int i;Data* tmp;
tmp=tab->data[index];//index是根结点在数组中的索引
for(i=2*index+1;i<bound;i=2*i+1)
{
if((tab->data[i]->num<tab->data[i+1]->num)&&(i+1<bound))
//如果左结点小于右结点 将位置标记在右结点
i++;
if(tab->data[i]->num>tmp->num)//如果孩子结点大于父亲结点 就子结点赋值于父亲结点 {
tab->data[index]=tab->data[i];
index=i;//记录孩子结点的顺序表位置
}
else
break;
}
tab->data[index]=tmp;
}
void pileSort(L* tab)
{
int i,j;
for(i=tab->len/2-1;i>=0;i--)//先构造大根堆
adjustHeap(tab,i,tab->len);
//每次将堆顶元素与末尾元素进行交换 将大的元素放在最后 这样整个顺序表成升序
for(i=tab->len-1;i>0;i--){
Data* temp=tab->data[i];//堆顶与末尾交换
tab->data[i]=tab->data[0];
tab->data[0]=temp;
adjustHeap(tab,0,i);//每次都顺序表0开始i为边界在0~i 的范围内重新调整堆
}
}
时间复杂度O(NlogN),空间复杂度O(1),不稳定
7、归并排序
基本思想：采用分治思想将数组不断进行拆分，直到数组的大小为2，
代码
void mergeSort(L* tab,int start,int mid,int end){
int len1=mid-start+1;
int len2=end-mid;
Data* arr1[len1];
Data* arr2[len2];
int i;
for(i=0;i<len1;i++)
arr1[i]=tab->data[start+i];//复制数组
for(i=0;i<len2;i++)
arr2[i]=tab->data[mid+1+i];
int k=0,l=0,r=0;
for(k=start;l<len1&&r<len2;k++)//k是tab的下标 {
if(arr1[l]->num<arr2[r]->num)//数组1的该元素小于数组2改元素 放前面{
tab->data[k]=arr1[l];
l++;
}else{
tab->data[k]=arr2[r];
r++;
}
}
if(l<len1)//如果数组1有剩余 直接复制{
for(;l<len1;l++){
tab->data[k]=arr1[l];
k++;
}
}
if(r<len2)//如果数组有剩余 直接复制{
for(;r<len2;r++){
tab->data[k]=arr2[r];
k++;
}
}
}
void divide(L* tab,int start,int end){
if(start>=end)
return;
int mid=(start+end)/2;
divide(tab,start,mid);
divide(tab,mid+1,end);
mergeSort(tab,start,mid,end);
}
时间复杂度：O(NlogN)
空间复杂度：O(n) 稳定