数据结构排序总结

楼主^#

更多发布于：2022-11-09 19:23

1.插入排序：直接插入排序（稳定）希尔排序（不稳定）

直接插入排序时间复杂度 O（n^2) 空间O（1）稳定的
void InsertSort(int A[],int n)
{
   int i,j,temp;
   for(i=1; i<n; i++)
   if(A<A[i-1]) //A的关键字小于前面一个
   {
   temp = A;

   for(j=i-1; j>=0 && A[j]>temp; --j)//从i-1的位置往左边检查是否已经排好序了，当j小于0时，退出这一层循环
   A[j+1]=A[j]; //所有大于temp的元素都要往后移

   A[j+1] = temp; //排好序后，将temp的值保存到第j+1的位置
   }
}

//带哨兵：将数组序号为0的位置空出来
void InsertSort(int A[],int n)
{
   int i,j;
   for(i=2; i<=n; i++)
   if(A<A[i-1]) //A的关键字小于前面一个
   {
   A[0] = A; //将元素复制到哨兵的位置

   for(j=i-1; A[0]<A[j]; --j)//从i-1的位置往左边检查是否已经排好序了，当j小于0时，退出这一层循环
   A[j+1]=A[j]; //所有大于a[0]的元素都要往后移

   A[j+1] = A[0]; //排好序后，将A[0]的值保存到第j+1的位置
   }
}

void InsertSort(Sqlist *L)
{
   int i,j;
   for(i=2; i<=L->length; i++)
   {
   L->A[0] = L->A //将元素复制到哨兵的位置
   j = i-1; //剩余的元素
   while(L->A[0].key < L->A[j].key) //检查哨兵位置的元素是否小于所有的剩下元素
   {
   L->A[j+1] = L->A[j]; //剩余元素后移
   j--;
   }
   L->A[j+1] = L->A[0]; //将哨兵元素插入到相应的位置
   }
}

希尔排序（可以D=n/2）时间复杂度未知，最坏O（n^2)此时就是直接插入排序空间O（1）不稳定
按规定的增量D 将表分割成若干个特殊“子表”，对每一个子表进行直接插入排序，再缩小增量D，重复直到D=1

void shellSort(int A[],int n)
{
   int d,i, j;
   for(d = n/2; d>=1; d=d/2) //增量（步长）发生变化
   for(i=d+1; i<=n; i++) //A[0]只是暂时存放数据，并不是哨兵
   if(A < A[i-d]) //将A插入到有序增量子表 {
   A[0] = A; //暂存到A[0]
   for(j=i-d; j>0 && A[0]<A[j]; j=j-d)
   A[j+d] = A[j]; //记录后移，查找插入的位置
   A[j+d] = A[0] //插入到合适的位置
   }//if
}

void shellSort(Sqlist *L,int d)
{
   int j, k ;
   for(j=d+1; j<=L->length; j++)
   {
   L->A[0] = L->A[j];
   k=j-d;
   while(k>0 && L->A[0].key = L->A[j].key)
   {
   L->A[k+d] = L->A[k];//记录后移，查找插入的位置
   k=k-d;
   }
   L->A[k+d] = L->A[0]; //插入到合适的位置
   }
}

2.归并排序将两个或多个有序序列合并成一个有序序列
   时间O(nlogn) 空间O(n) ：因为构造了辅助数组是稳定的
2路归并 ---将一个数组中前后相邻的两个有序序列归并为一个
K路归并
//构造一个辅助数组B，存放有序子序列
int *B=(int *)malloc(n*sizeof(int)); //其大小 n 与数组A相同

//归并过程 A[low;......;mid]和A[mid+1;...;high]已经各自有序，现将两部分进行归并
void Merge(int A[], int low, int mid, int high)
{
   int i,j,k; //i 指向辅助数组B中【low;......;mid】部分 j指向辅助数组B中【mid+1;...;high】部分
   for(k=low; k<=high; k++) // k 指向辅助数组A中【low;......;high】部分
   B[k] = A[k]; //将A中所有元素复制到B中

   for(i=low, j=mid+1, k+i; i<=mid && j<=high; k++) //归并
   {
   if(B <= B[j])
   A[k] = B[i++]; //将i 指向的部分中较小的值复制到A中
   else
   A[k] = B[j++]; //将j 指向的部分中较小的值复制到A中
   }//for
   while(i <= mid) A[k++] = B[i++]; //没有归并完的部分直接复制到尾部
   while(j <= mid) A[k++] = B[j++];
}

//归并排序
void MergeSort(int A[], int low, int high)
{
   if(low < high)
   {
   int mid=(low+high)/2; //将原序列，从中间划分
   MergeSort(A,low,mid); //对A[low;......;mid]左半部分，进行归并排序
   MergeSort(A,mid+1,high); //对A[mid+1;...;high]右半部分，进行归并排

   Merge(A,low,mid,high); //归并
   }//if
}

3.选择排序：在待排序元素中，每一趟取关键字最小（最大）的加入到有序子序列中 --简单选择排序堆排序

简单选择排序每一趟取关键字最小的加入到有序子序列中，最后一个元素不需要处理时间O（n^2）空间O（1）不稳定

void swap(int &a,int &b) //共需要移动元素3次
{
   int temp = a;
   a = b;
   b = temp;
}
void SelectSort(int A[],int n)
{
   for(int i=0;i<n-1;i++) //共需要进行n-1趟排序
   int min = i;
   for(int j=i+1 ; j<n ; j++) //继续在A【】中寻找最小的元素
   if(A[j] < A[min]) min = j; //更新最小值
   if(min != i)
   swap(A,A[min]); //与第i个记录交换位置
}

堆：可看作顺序存储的“完全二叉树” 总的时间复杂度O（n * logn）结点 i 的左孩子 2i ，右孩子 2i+1 ，父节点 i/2 ，其编号<=n/2的结点都是分支结点空间O（1）
大根堆：根大于等于左右子树堆顶元素一定是序列中的最大值 ---排序结果：递增且不稳定小根堆：根小于等于左右子树堆顶元素一定是序列中的最小值 ---排序结果：递减
思想：（建立大根堆）建堆：编号<= n/2的节点依次下坠，自底向上处理分支节点 ---小元素组层“下坠”，与关键字更大的孩子交换时间复杂度O（n）
排序：将建堆后的堆顶元素加入到子序列中，同时和原堆底元素交换位置，时间复杂度O（n * logn）在重新进行建堆操作，直到恢复“大根堆的特性”，重复操作n-1次

//建立大根堆
void BuildMaxHeap(int A[],int len){
   for(int i=len/2 ; i>0 ; i--) //从后往前调整非终端节点 HeadAdjust(A,i,len); //调用调整大根堆函数
}

//堆排序void HeapSort(int A[],int len)
{ BuildMaxHeap(A,len); //调用初始建堆函数
   for(int i=len; i>1; i--) //n-1趟交换和建堆的过程 {
   swap(A , A[1]); //将堆顶元素和堆底元素交换 HeadAdjust(A, 1, i-1); //将剩余待排序的元素，重新整理成堆
   }

}

//将以 K 为根的子树调整为大根堆void HeadAdjust(int A[], int k, int len)
{ A[0] = A[k]; //A[0]暂时存放子树的根节点
   for(int i=2*k ; i<=len; i*=2) //沿K 较大的子节点进行筛选 {
   if(i<len && A<A[i+1]) i++ //沿K 较大的子节点
   if(A[0]>=A) break; //筛选结束 else{
   A[k] = A //将A 调整到双亲节点 k = i; //修改K值继续向下筛选
   } }
   A[k] = A[0]; //被筛选的节点放入最终位置}

4.”交换“排序 -- 根据序列中两个元素关键字的比较结果，来对换这两个记录在序列中的位置-----冒泡排序快速排序

冒泡排序---每一趟排序都把大的元素往上浮时间复杂度 O（n^2）空间复杂度 O（1）稳定的
void swap(int &a,int &b) //每次交换需要移动3个元素
{
   int temp;
   temp=a;
   a=b;
   b=temp;
}
void Bubble_Sort(int A[],int n)
{
   int flag;
   for(int i=0;i<n-1;i++)
   {
   flag=0; //表示冒泡排序是否发生交换，设置的标记
   for(int j=n-1;j>i;j--) //进行一趟冒泡排序
   if(A[j-1]>A[j]) //逆序的情况
   swap(A[j-1],A[j]); //交换位置
   flag=1;
   }
   if(flag==0) //已经排序好了
   return 0;
}

快速排序 ---选择一个基准，将所有更小于基准的元素放于右边，将更大的放于左边，重复操作不稳定
时间复杂度O（n*递归层数）最坏O（n*logn）最好O（n*n）空间复杂度O（递归层数）

int Partition(int A[],int low,int high)
{
   int pivot = A[low]; //将第一个元素作为基准（枢纽）
   while(low<high) //用low,high来确定基准的最终位置
   {
   while(low<high && A[high]>=pivot) //在high部分（右端）寻找比基准要小的元素
   high--;
   A[low] = A[high]; //使其移动到low部分（左端）

   while(low<high && A[low]<=pivot) //在low部分（左端）寻找比基准要小的元素
   low++;
   A[high] = A[low]; //使其移动到high部分（右端）
   }//while
   A[low] = pivot; //基准存放的最终位置
   return low; //返回其最终位置
}

void QuickSort(int A[],int low,int high)
{
   if(low<high) //跳出递归的条件
   {
   int pivotpos = Partition(A,low,high); //将原序列划分为左右两个部分
   QuickSort(A,low,pivotpos-1); //对左子表继续进行划分
   QuickSort(A,pivotpos+1,high); //对右子表继续进行划分
   }
}

稳定性总结：
插入排序：直接插入排序（稳定）希尔排序（不稳定）
归并排序：稳定的
交换排序冒泡排序（稳定）快速排序（不稳定）
选择排序：简单选择排序（不稳定）堆排序（不稳定）

喜欢1

数据结构排序总结

最新喜欢：