算法===》==》=》排序(内部排)

一些最基本的排序算法:插入排序交换排序选择排序@插入排序:1-直接插入排序:从前端插入从后端插入2-希尔(Shell)排序1-直接插入排序:从前端插入:intarr[]=999,1,2,5,8,4,3,9,7};//"999"是一个容储器(arr[0]是一个监视哨),不参与排序。voidInsertSort(intn)inti,j;for(i=2;i<=n;i )//进行n-1次排序arr...

算法===》==》=》排序(内部排)

在这里插入图片描述一些最基本的排序算法:

  • 插入排序
  • 交换排序
  • 选择排序

@ 插入排序:

1-直接插入排序:

  • 从前端插入
  • 从后端插入

2-希尔(Shell)排序

1-直接插入排序:

  • 从前端插入:
int arr[]={999,1,2,5,8,4,3,9,7};//"999"是一个容储器(arr[0]是一个监视哨),不参与排序。void InsertSort(int n){int i,j;for(i=2;i<=n;i  )//进行n-1次排序{arr[0]=arr[i];//设置监视哨---减少扫描量,提高效率。j=i-1;//j代表有序序列的最后一个元素while(arr[0]<arr[j]){arr[j 1]=arr[j];//记录后移j--;}arr[j 1]=arr[0];//把存放在arr[0]中的原记录插入到正确位置}}
  • 从后端插入:
int arr[]={0,1,2,5,8,4,3,9,7,999};//"999"是一个容储器(arr[n 1]是一个监视哨),"0"是填补i=0的空白位置,"999"与"0"均不参与排序。void InsertSort(int n)//从第n-1个元素开始向它前面插入,直到第一个元素插入为止。{int i,j;for(i=n-1;i>=1;i--)//进行n-1次排序{arr[n 1]=arr[i];//设置监视哨j=i 1;//j代表有序序列的最后一个元素while(arr[n 1]>arr[j]){arr[j-1]=arr[j];//记录前移j  ;}arr[j-1]=arr[n 1];//把存放在arr[n 1]中的原记录插入到正确位置}}

2-希尔(Shell)排序==>直接插入排序的改进版

void InsertSort(int n){int i,j,d;for(d=n/2;d>=1;d=d/2)//进行n-1次排序{for(i=d 1;i<=n;i  ){arr[0]=arr[i];//设置监视哨j=i-d;//前后位置的增量为d,而不是1while(j>0&&arr[0]<arr[j]){arr[j d]=arr[j];//记录后移,查找插入位置j=j-d;}arr[j d]=arr[0];//插入}}}

------》源代码:

#include<iostream>using namespace std;//1.数组的初始化:int arr[]={999,1,2,5,8,4,3,9,7};//"999"是一个容储器(arr[0]是一个监视哨),不参与排序。//2.希尔排序:void InsertSort(int n){int i,j,d;for(d=n/2;d>=1;d=d/2)//进行n-1次排序{for(i=d 1;i<=n;i  ){arr[0]=arr[i];//设置监视哨j=i-d;//前后位置的增量为d,而不是1while(j>0&&arr[0]<arr[j]){arr[j d]=arr[j];//记录后移,查找插入位置j=j-d;}arr[j d]=arr[0];//插入}}}void Show_arr(int n){int i;for(i=1;i<=n;i  )cout<<arr[i]<<'\t';cout<<endl;}void main(){InsertSort(8);Show_arr(8);}

直接插入排序的算法的时间复杂度为O(n^2),直接插入排序是一种稳定的排序方法。而shell_sort的算法的时间复杂度为O(n* log2^n)~ O(n ^2) 大略为O(n^(3/2)),shell_sort不是一种稳定的排序方法

@交换排序:

  • 冒泡排序
  • 快速排序

1- 冒泡排序:

void Bubble_Sort(int *a,int n){int  i, j, t;for(i=0;i<n-1;i  ){for(j=0;j<n-i-1;j  )if(a[j]>a[j 1]){t=a[j];a[j]=a[j 1];a[j 1]=t;}}}

2-快速排序:

void Quick_Sort(int low,int high){if(low>=high)return ;int i=low,j=high;//避免引起歧义arr[0]=arr[low];while(i<j){while(i<j&&arr[0]<=arr[j])//"i<j"绝对不能省,此处与外循环的含义不同j--;arr[i]=arr[j];while(i<j&&arr[i]<=arr[0])i  ;arr[j]=arr[i];}arr[i]=arr[0];Quick_Sort(low,i-1);Quick_Sort(i 1,high);}

------》源代码:

#include<iostream>using namespace std;//1.数组的初始化:int arr[]={0,1,2,5,8,4,3,9,7};//2.快速排序:一个形象的比喻-》“选取一个中间点,两边互相扔石头”void Quick_Sort(int low,int high){if(low>=high)return ;int i=low,j=high;//避免引起歧义arr[0]=arr[low];while(i<j){while(i<j&&arr[0]<=arr[j])//"i<j"绝对不能省,此处与外循环的含义不同j--;arr[i]=arr[j];while(i<j&&arr[i]<=arr[0])i  ;arr[j]=arr[i];}arr[i]=arr[0];Quick_Sort(low,i-1);//这里采用递归来化简算法的难度Quick_Sort(i 1,high);}void Show_arr(int n){int i;for(i=1;i<=n;i  )cout<<arr[i]<<'\t';cout<<endl;}void main(){Quick_Sort(1,8);Show_arr(8);}

冒泡排序的算法的时间复杂度为O(n^2),是一种稳定的排序方法。
快速排序的算法的时间复杂度为O(n* log2^n)~ O(n ^2),不是一种稳定的排序方法。

@选择排序:

  • 直接选择排序
  • 堆排序

直接选择排序:

void Sort(int *a,int len){int i,j,min,t;for(i=0;i<len-1;i  ){for(min=i,j=i 1;j<len;j  )if(a[min]>a[j]){min=j;}if(min!=i){t=a[i];a[i]=a[min];a[min]=t;}}}

------》源代码:

#include<iostream>using namespace std;//1.数组的初始化:int arr[]={1,2,5,8,4,3,9,7};//2.选择排序:void Sort(int *a,int len){int i,j,min,t;for(i=0;i<len-1;i  ){for(min=i,j=i 1;j<len;j  )if(a[min]>a[j]){min=j;}if(min!=i){t=a[i];a[i]=a[min];a[min]=t;}}}void Show_arr(int n){int i;for(i=0;i<n;i  )cout<<arr[i]<<'\t';cout<<endl;}void main(){Sort(arr,8);Show_arr(8);}

堆排序:==>选择排序的改进版
*什么是堆?—
堆是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的数值或索引总是小于(或者大于)它的父节点。
堆排序的生成及其排序原理:
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
堆排序的实现:

void Adjust(int i,int n)//i代表待调整元素的下标,n代表最后一元素的下标。{int j;arr[0]=arr[i];while(i<n&&2*i<=n){j=2*i;//j为i左孩子下标if(j<n&&arr[j]>arr[j 1])j  ;//j指向较小的孩子if(arr[0]>arr[j]){arr[i]=arr[j];i=j;}elsebreak;}arr[i]=arr[0];}void Build_Heap(int n){int i;for(i=n/2;i>0;i--)Adjust(i,n);}void Show_arr(int n){int i;for(i=1;i<=n;i  )cout<<arr[i]<<'\t';cout<<endl;}void Heap_Sort(int n){int i,t;Build_Heap(n);cout<<"初始堆积树:"<<endl;Show_arr(8);cout<<endl;for(i=n;i>1;i--){t=arr[1];arr[1]=arr[i];arr[i]=t;cout<<endl<<"第  "<<n-i 1<<"趟:"<<endl;Show_arr(8);Adjust(1,i-1);}}

------》源代码:

#include<iostream>using namespace std;//1.数组的初始化:int arr[]={0,1,2,5,8,4,3,9,7};/*2.堆积树的调整过程:从二叉树的叶子节点处往上逐一比较来建立最大堆积树:*/void Adjust(int i,int n)//i代表待调整元素的下标,n代表最后一元素的下标。{int j;arr[0]=arr[i];while(i<n&&2*i<=n){j=2*i;//j为i左孩子下标if(j<n&&arr[j]>arr[j 1])j  ;//j指向较小的孩子if(arr[0]>arr[j]){arr[i]=arr[j];i=j;}elsebreak;}arr[i]=arr[0];}//3.堆积树的建立:void Build_Heap(int n){int i;for(i=n/2;i>0;i--)Adjust(i,n);}//显示:void Show_arr(int n){int i;for(i=1;i<=n;i  )cout<<arr[i]<<'\t';cout<<endl;}//4.堆积排序:void Heap_Sort(int n){int i,t;Build_Heap(n);cout<<"初始堆积树:"<<endl;Show_arr(8);cout<<endl;for(i=n;i>1;i--){t=arr[1];arr[1]=arr[i];arr[i]=t;cout<<endl<<"第  "<<n-i 1<<"趟:"<<endl;Show_arr(8);Adjust(1,i-1);}}void main(){Show_arr(8);cout<<endl;Heap_Sort(8);}

直接选择排序的算法的时间复杂度为O(n^2),由于直接选择排序交换次数少,当记录占用的字节数较多时,通常比直接插入排序的执行速度要快一些。但它却并不是一种稳定的排序方法,综合来看其性价比 较低.
堆排序方法对记录数较小的排序效果并不理想,但对于n较大的文件很有意义,因为其运行时间主要建立在初始建堆和反复调整堆上。
建堆的时间复杂度与堆所对应的完全二叉树的深度的数量级log2^n 有关,而调用数量级为n,所以整个堆排序的时间复杂度为O(n* log2^n)。在空间复杂度方面,堆排序只需要一个辅助空间,为O(1)。此外,堆排序并不是稳定的排序哦。

*ps:在算法的设计中排序的方法有很多种,但具体情况还需要具体分析,在情景中应当采取最合适的排序算法。

源文地址:https://www.guoxiongfei.cn/csdn/4881.html
0