数据结构和算法解析：排序问题简易总结
直接插入排序
直接插入排序（Straight Insertion Sorting）的基本思想：在要排序的一组数中，假设前面(n-1) [n>=2] 个数已经是排好顺序的，现在要把第n个数插到前面的有序数中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。
直接插入排序是一种稳定的排序方法,最好的时间复杂是O(n)也就是已经排好的序列,最差的时间复杂度是O(n^2)逆序
//插入排序是一种稳定的排序方法,最好的时间复杂是O(n)也就是已经排好的序列,最差的时间复杂度是O(n^2)逆序
public void insertSort(int nums[]){
int tmp;
for(int i=1;i<nums.length;i++){
int j=i;
while (j>0 && nums[j]<nums[j-1]){
tmp=nums[j];
nums[j]=nums[j-1];
nums[j-1]=tmp;
j--;
}
}
}
希尔排序
- 希尔排序(Shell’s Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。
- 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
算法思想
对于直接插入排序问题，数据量巨大时。将数的个数设为n，取奇数k=n/2，将下标差值为k的数分为一组，构成有序序列。再取k=k/2 ，将下标差值为k的书分为一组，构成有序序列。重复第二步，直到k=1执行简单插入排序。
希尔排序是一种非常不稳定的排序方法，它的时间复杂度为O(n^（1.3—2）)
//希尔排序是一个不稳定的排序算法,它的时间复杂度为O(n^（1.3—2）)
public void shellSortHelper(int nums[],int incr){
int tmp;
for(int i=incr;i<nums.length;i+=incr){
int j=i;
while (j>0 && nums[j]<nums[j-incr]){
tmp=nums[j];
nums[j]=nums[j-incr];
nums[j-incr]=tmp;
j-=incr;
}
}
}
//希尔排序
public void shellSort(int nums[]){
for(int i=nums.length/2;i > 0;i/=2){
shellSortHelper(nums,i);
}
}
选择排序
-
常用于取序列中最大最小的几个数时。
(如果每次比较都交换，那么就是交换排序；如果每次比较完一个循环再交换，就是简单选择排序。) -
遍历整个序列，将最小的数放在最前面。
-
遍历剩下的序列，将最小的数放在最前面。
-
重复第二步，直到只剩下一个数。
选择排序的时间复杂度为O(n^2) 选择排序不是一个稳定的排序
//交换排序是一种稳定的排序方法，最好最坏的时间复杂度都是O(n^2)
public void swapSort(int nums[])
{
int tmp;
for(int i=0;i<nums.length;i++){
for(int j=i+1;j<nums.length;j++){
if(nums[i]>nums[j]){
tmp=nums[j];
nums[j]=nums[i];
nums[i]=tmp;
}
}
}
}
//选择排序是一种不稳定的排序方法，最好最坏的时间复杂度都是O(n^2)
public void selectSort(int nums[]){
for(int i=0;i<nums.length;i++){
int values=nums[i];
int position=i;
for(int j=i+1;j<nums.length;j++){
if(nums[j]<values){
values=nums[j];
position=j;
}
}
//swap
nums[position]=nums[i];
nums[i]=values;
}
}
冒泡排序
很简单，用到的很少，据了解，面试的时候问的比较多！将序列中所有元素两两比较，将最大的放在最后面。将剩余序列中所有元素两两比较，将最大的放在最后面。重复第二步，直到只剩下一个数。
冒泡排序的时间复杂度为O(n^2) 冒泡排序是一个稳定的排序
//冒泡排序 一种稳定的排序算法，最好最坏的时间复杂度都是O(n^2)
public void bubbleSort(int nums[]){
int tmp;
for(int i=0;i<nums.length;i++){
for (int j=0;j<nums.length-i-1;j++){
if(nums[j]>nums[j+1]){
tmp=nums[j+1];
nums[j+1]=nums[j];
nums[j]=tmp;
}
}
}
}
快速排序
要求时间最快时。
- 选择第一个数为p，小于p的数放在左边，大于p的数放在右边。
- 递归的将p左边和右边的数都按照第一步进行，直到不能递归。
快速排序是由一种不稳定的排序算法，最好的时间复杂度是O(nLogN)，最差时间复杂度是O(n^2)
//快速排序是由一种不稳定的排序算法，最好的时间复杂度是O(nLogN)，最差时间复杂度是O(n^2)
private void quickSortHelper(int nums[],int start,int end){
if(start>end) return;
int high=end;
int low=start;
int target=nums[start];
while (low<high){
while (low<high && nums[high]>=target){
high--;
}
nums[low]=nums[high];
while (low<high && nums[low]<=target){
low++;
}
nums[high]=nums[low];
}
nums[low]=target;
quickSortHelper(nums,start,low-1);
quickSortHelper(nums,low+1,end);
}
public void quickSort(int nums[])
{
quickSortHelper(nums,0,nums.length-1);
}
归并排序
速度仅次于快速排序，内存少的时候使用，可以进行并行计算的时候使用。
- 选择相邻两个数组成一个有序序列。
- 选择相邻的两个有序序列组成一个有序序列。重复第二步，直到全部组成一个有序序列。
归并排序,是一种不稳定的排序是算法这个算法的时间复复杂度都是O(NlogN)
//归并排序,是一种不稳定的排序是算法这个算法的时间复复杂度都是O(NlogN)
public void mergeSrot(int nums[],int start,int end){
if(start>=end) return;
int mid=(start+end)/2;
mergeSrot(nums,start,mid);
mergeSrot(nums,mid+1,end);
mergeSrotHelper(nums,start,mid,end);
}
// 将两个有序序列归并为一个有序序列(二路归并)
private void mergeSrotHelper(int[] nums, int start, int mid, int end) {
int[] arr=new int[end+1];
int low=start;
int left=start;
int center=mid+1;
while (left<=mid && center<=end){
arr[low++] = nums[left] <= nums[center] ? nums[left++] : nums[center++];
}
while (left<=mid){
arr[low++]=nums[left++];
}
while (center<=end){
arr[low++]=nums[center++];
}
for(int i=start;i<=end;i++){
nums[i]=arr[i];
}
}
堆排序
对简单选择排序的优化。
- 将序列构建成大顶堆。
- 将根节点与最后一个节点交换，然后断开最后一个节点。
- 重复第一、二步，直到所有节点断开。
//堆排序
private boolean isLeaf(int nums[],int pos)
{
//没有叶子节点
return pos*2+1>=nums.length;
}
private void swap(int[] nums,int pos1,int pos2)
{
int tmp;
tmp=nums[pos2];
nums[pos2]=nums[pos1];
nums[pos1]=tmp;
}
private void shiftdown(int[] nums,int pos)
{
while(!isLeaf(nums,pos))
{
int left=pos*2+1;
int right=pos*2+2;
if(right<nums.length)
{
left=nums[left]>nums[right]?left:right;
}
//是否需要调整堆
if(nums[pos]>=nums[left]) return;
swap(nums,pos,left);
pos=left;
}
}
public void buildHeap(int nums[])
{
for(int i=nums.length/2-1;i>=0;i--)
{
shiftdown(nums,i);
}
}
public void heapSort(int nums[])
{
for(int i=nums.length-1;i>=0;i--)
{
swap(nums,0,i);
shiftdown(nums,i);
}
}
总结
一、稳定性:
- 稳定：冒泡排序、插入排序、归并排序和基数排序
- 不稳定：选择排序、快速排序、希尔排序、堆排序
二、平均时间复杂度
-
O(n^2):直接插入排序，简单选择排序，冒泡排序。
-
在数据规模较小时（9W内），直接插入排序，简单选择排序差不多。当数据较大时，冒泡排序算法的时间代价最高。性能为O(n^2)的算法基本上是相邻元素进行比较，基本上都是稳定的。
-
O(nlogn):快速排序，归并排序，希尔排序，堆排序。
其中，快排是最好的，其次是归并和希尔，堆排序在数据量很大时效果明显。
三、排序算法的选择
- 数据规模较小
-
（1）待排序列基本序的情况下，可以选择直接插入排序；
-
（2）对稳定性不作要求宜用简单选择排序，对稳定性有要求宜用插入或冒泡
- 数据规模不是很大
-
（1）完全可以用内存空间，序列杂乱无序，对稳定性没有要求，快速排序，此时要付出log（N）的额外空间。
-
（2）序列本身可能有序，对稳定性有要求，空间允许下，宜用归并排序
- 数据规模很大
-
（1）对稳定性有求，则可考虑归并排序。
-
（2）对稳定性没要求，宜用堆排序
- 序列初始基本有序（正序），宜用直接插入，冒泡