一、插入排序

1.1 直接插入排序

        空间复杂度:。

        时间复杂度:。在最好情况下,表中元素已经有序,此时每插入一个元素,都只需要比较一次而不用移动元素,因此时间复杂度为。

        稳定性:每次插入元素时总是从后向前先比较再移动,所以不会出现相同元素相对位置发生变化的情况。即直接插入排序是一个稳定的排序方法。
public class InsertSort { public static void insertSort(int[] array,int n) {
int i=0; int j=0; for(i=1;i<n;i++) {//待排序的无序区 int t=array[i];
for(j=i-1;j>=0&&t<array[j];j--) {//已经排好序的有序区 array[j+1]=array[j]; }
array[j+1]=t; } } public static void main(String[] args) { int[] a=
{4,0,2,3,1}; insertSort(a, 5); for(int n:a) { System.out.print(n+" "); } } }
 

1.2 希尔排序

    空间复杂度:。

   时间复杂度:当n在某个特定范围时,希尔排序的时间复杂度约为。在最坏情况下希尔排序排序的时间复杂度为。

   稳定性:当相同关键字的记录被划分到不同的子表时,可能会改变他们之间的相对次序,因此希尔排序是一个不稳定的排序方法。
public static void shell(int value[],int n,int start,int step)     {       
 int i = 0;         for(i = start + step;i < n;i += step)         {           
 int temp = value[i];             int j = 0;             for(j = i - step;j >=
start && value[j] > temp;j -= step)             {                 value[j +
step] = value[j];             }             value[j + step] = temp;         }
    }     public static void shellSort(int value[],int n)     {         int
step = n / 2;         while(step > 0)         {             int i = 0;         
   for(i = 0;i < step;i++)             {                 shell(value,n,i,step);
            }             step /= 2;         }     }     public static void
main(String[] args){         int value[] = {8,3,6,2,4,5,7,1,9,0};       
 shellSort(value,10);         System.out.println("排序后的结果为:");         int i =
0;         for(;i < 10;i++) {             System.out.print(value[i]);         }
       }
二、交换排序

2.1 冒泡排序

空间复杂度:。

时间复杂度:最坏情况下为,最好情况下为(表中元素基本有序)。其平均时间复杂度为。

稳定性:稳定。
public class BubbleSort { public static void bubbleSort(int[] array,int n) {
for(int i=0;i<n-1;i++) { boolean flag=false; for(int j=n-1;j>i;j--) {
if(array[j-1]>array[j]) { int t=array[j-1]; array[j-1]=array[j]; array[j]=t;
flag=true; } } if(flag==false) { return; } } } public static void main(String[]
args) { int[] a= {3,8,7,1,2,5,6,4}; bubbleSort(a, 8); for(int n:a) {
System.out.print(n+" "); } } }
2.2 快速排序

       空间复杂度:由于快速排序是递归的,需要借助一个递归工作栈来保存每一层递归调用的的必要信息,其容量应与递归调用的最大深度一致。最好情况下为
。最坏情况下,因为要进行n-1次递归调用,所以栈的深度为。平均情况下,栈的深度。

       时间复杂度:快速排序的最坏情况发生在两个区域分别包含n-1个元素和0个元素时,这种最大程度的不对称性若发生在每一层递归上,即对应于初始排序表基本有序或基本逆序时,就得到最坏情况下的时间复杂度。最理想情况下(平衡划分),时间复杂度为
。快速排序是所有内部排序算法中平均性能最优的排序算法。

      稳定性:不稳定。
      
public class QuickSort { public static void quickSort(int[] array,int low,int
high) { if(low<high) { int index=partition(array,low,high); quickSort(array,
low, index-1); quickSort(array, index+1, high); } } public static int
partition(int[] array,int low,int high) { int pivot=array[low]; while(low<high)
{ while(low<high&&array[high]>=pivot) { --high; } array[low]=array[high];
while(low<high&&array[low]<=pivot) { low++; } array[high]=array[low]; }
array[low]=pivot; return low; } public static void main(String[] args) { int[]
a= {3,8,7,1,2,5,6,4}; quickSort(a, 0,7); for(int n:a) { System.out.print(n+"
"); } } }
三、选择排序

3.1 简单选择排序

       空间复杂度:。

       时间复杂度:从下面代码看出,简单选择排序过程,元素移动操作次数很少,不会超过次
(一次swap需要3次元素移动),最好的情况是移动0次,此时对应的表已经有序。但元素比较次数与序列初始状态无关,始终是次。所以时间复杂度是。

       稳定性:不稳定。
      
public class SelectSort { public static void selectSort(int[] array,int n) {
for(int i=0;i<n-1;i++) { int min=i; for(int j=i+1;j<n;j++) {
if(array[j]<array[min]) { min=j; } } if(min!=i) { int temp=array[min];
array[min]=array[i]; array[i]=temp; } } } public static void main(String[]
args) { int[] a= {3,8,7,1,2,5,6,4}; selectSort(a,8); for(int n:a) {
System.out.print(n+" "); } } }
 3.2 堆排序

    空间复杂度:仅用常数个辅助单元,所以空间复杂度为。

    时间复杂度:在最好、最坏和平均情况下,堆排序的时间复杂度为。

    稳定性:不稳定。

四、归并排序

4.1 二路归并排序

      空间复杂度:Merge()操作中,由于辅助空间刚好要占用n个单元,但每一趟归并后这些空间就被释放了,所以归并排序的空间复杂度为。

      时间复杂度:每一趟归并的时间复杂度为,共需进行趟归并,所以算法的时间复杂度为。

      稳定性:稳定。  
public class MergeSort { public static void mergeSort(int[] array,int low,int
high) { if(low<high) { int mid=(low+high)/2; mergeSort(array, low, mid);
mergeSort(array, mid+1, high); merge(array,low,mid,high); } } public static
void merge(int[] array,int low,int mid,int high) { int[] num=new
int[array.length]; for(int k=low;k<=high;k++) { num[k]=array[k]; } int i=low;
int j=mid+1; int k=i; for(;i<=mid&&j<=high;k++) { if(num[i]<num[j]) {
array[k]=num[i++]; }else { array[k]=num[j++]; } } while(i<=mid) {
array[k++]=num[i++]; } while(j<=high) { array[k++]=num[j++]; } } public static
void main(String[] args) { int[] a= {3,8,7,1,2,5,6,4}; mergeSort(a, 0,7);
for(int n:a) { System.out.print(n+" "); } } }
 

技术
©2019-2020 Toolsou All rights reserved,
笔记十四:研发管理中激励他人的第二大障碍Keras训练数据加载实现小结冲突声明(conflicting declaration)解决11-5 指定位置输出字符串一元线性回归与多元线性回归理论及公式推导Vue el-select 获取label值Hackbar 使用教程Golang数组平分,数组拆分,数组分组LED 滚动文字Centos7 下mysql8.0的安装以及修改初始密码;