首页 > 代码库 > 排序算法

排序算法

2024-07-07 07:32:41   225人阅读

一、插入排序

1.直接插入排序

算法稳定，时间复杂度为O(n^2)，空间移动复杂度为O(n2)

如果序列是有序的，最好的时间复杂度为O(n)

void insertSort(int data[],int n)
{
  for(int i=1;i<n;i++)
  {
      int j = i - 1;
      int temp = data[i];
      while(j>=0&&data[j]>temp) 
     {
         data[j] = data[j-1];
         j--;
     }  
     data[j+1] = temp;  
  }    
}

2.折半插入排序

查找插入位置采用折半查找法。

算法稳定，时间复杂度为O(nlog2n)，空间移动复杂度为O(n2)

void BinaryinsertSort(int data[],int n)
{
  for(int i=1;i<n;i++)
 {
      int left = 0;
      int right = i-1;
      int temp = data[i];
      while(left<=right)
      {
           int mid = (left+right)/2 ;
           if(data[mid]>temp)              //判断是否影响稳定性。
              rigth = mid - 1;
else 
              left = mid + 1;
      }    
      for(int j=i-1;j>=left;j--)
            data[j+1] = data[j];
      data[left] = temp;
  }
}

3.希尔排序

将待排数据分组，组内进行直接插入排序。逐步减小分组数，最后再整体进行直接插入排序。

希尔排序的时间复杂度为介于O(nlog2n)与O(n*n)之间，大约为O(n1.3);

希尔排序算法是不稳定的。

二、交换排序

1.冒泡排序

时间复杂度为O(n*n),是稳定的排序算法。

2.快速排序

分治法的思想，最坏的情况是待排数据时有序的时候，此时会造成轴元素的一侧子序列的长度为0，另一侧的长度为n，此时时间复杂度为O(n*n)

空间复杂度主要是递归调用的栈的开销，最好的时候是O(logn),最坏的情况是O(n).

平均的时间复杂度为：O(nlogn);

该算法是不稳定的。

三、选择排序

1.简单选择排序

时间复杂度为O(n*n),空间复杂度为O(1)

是不稳定为排序算法。

2.堆排序

最大堆的调整函数为shiftdown()函数。

每次最多执行O(logn)次数据的交换，所以其时间复杂度为O(nlogn).

空间开销是O(1).

该算法是不稳定的。

四、归并排序

最坏的情况下的时间发复杂度也为O(nlogn),算法是稳定的。

空间复杂度为O(n).

 


联系
我们