面试中常问的排序算法

冒泡排序

大体思想是通过与相邻元素比较和交换来把小的数交换到最前面。

举个例子，对5,3,8,6,4这个无序序列进行冒泡排序。首先从后向前冒泡，4和6比较，把4交换到前面，序列变成5,3,8,4,6这个无序。同理4和8交换，序列变成5,3,4,8,6，3和4无需交换。5和3交换，变成3,5,4,8,6，这样一次冒泡就完成了，把最小的数3排的最前面了。对剩下的序列依次冒泡就会得到一个有序序列。冒泡的时间复杂度为O（n^2）

实现代码

public static void swap(int[] arr,int a,int b)
	{
		int temp=arr[a];
		arr[a]=arr[b];
		arr[b]=temp;
	}
	
	public static void bubbleSort(int[] arr)
	{
		if(arr.length==0||arr==null)
		{
			return;
		}
		for(int i=0;i<arr.length-1;i++)
		{
			for(int j=arr.length-1;j>0;j--)
			{
				if(arr[j]<arr[j-1])
				{
					swap(arr,j-1,j);
				}
			}
		}
	}

选择排序的思想是通过对整体的选择，把一次排序后最小的元素放在最前面。举个例子，对5,3,8,6,4这个无序序列进行简单选择排序，首先选择5以外的最小值来和5交换，也就是选择3 和5 交换，一次排序后就变成了3,5,8,6,4，对剩余的序列依次进行选择和交换，最终就会得到一个有序序列。其实选择排序可以看成冒泡排序的优化，因为目的相同，只是选择排序只有在确定了最小数的前提下才进行交换，大大减少了交换的次数。选择排序的时间复杂度为O（n^2）

实现代码：

public static void selectSort(int[] arr)
	{
		if(arr.length==0||arr==null)
		{
			return;
		}
		int minindex=0;
		for(int i=0;i<arr.length;i++)
		{
			int min = arr[i];
			for(int j=i+1;j<arr.length;j++)
			{
				if(arr[j]<min)
				{
					min=arr[j];
					minindex=j;
				}
			}
			swap(arr, i, minindex);
			
		}
		
	}

插入排序不是通过交换位置而是通过比较找到合适的位置插入元素来达到排序的目的。举个例子，对5,3,8,6,4这个无序序列进行简单插入排序，首先假设第一个数的位置是正确的，然后3要插到5的前面，把5后移一位，变成3,5,8,6,4。然后8不动，6插在8的前面，8后移一位，4插在5的前面，从5开始向后移一位。注意在插入一个数的时候要保证这个数前面的数已经有序。简单插入排序的时间复杂度也是O（n^2）

public static void insertSort(int[] arr)
	{
		if(arr.length==0||arr==null)
		{
			return;
		}
		
		for(int i=1;i<arr.length;i++)
		{
			int j=i;
			int value = arr[i];
			while(j>0&&arr[j-1]>value)
			{
				arr[j]=arr[j-1];
				j--;
			}
			arr[j]=value;
		}
		

快速排序

基本思想：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的。举个例子：对5,3,8,6,4这个无序序列进行快速排序，思想是右指针找到比基准小的，左指针找比基准数大的，交换之。5,3,8,6,4用5作为比较的基准，最终会把5小的移到5的左边，比5大的移到右边。5,3,8,6,4首先设置两个指针low,high,分别指向两端，high指针先扫描（因为基准5在左边），4比5小停止，然后low扫描，8比5大停止，交换low，high位置。5,3,4,6,8然后指针high在扫描，这时high扫描4时两指针相遇。停止然后交换4和基准数。4,3,5,6,8一次划分后叨叨了左边比5小，右边比5大的目的。之后对左右子序列递归排序，最终得到有序序列。

快速排序是不稳定的，其平均时间复杂度是O（nlogn）

实现代码：

public static int partition(int[] arr,int low,int high)
	{
		int pivo=arr[low];
		while(low<high)
		{
			while(low<high&&arr[high]>=pivo)
				high--;
			arr[low]=arr[high];
			while(low<high&&arr[low]<=pivo)
				low++;
			arr[high]=arr[low];
		}
		arr[low]=pivo;
		return low;
	}
	
	public static void quickSort(int[] arr,int low,int high)
	{
		if(low>=high)
			return;
		int pivo=partition(arr, low, high);
		quickSort(arr,low,pivo-1);
		quickSort(arr,pivo+1,high);
		
	}

堆排序：

堆排序是借助堆来实现的选择排序，思想同简单的选择排序，一下以大顶堆为例。注意：如果想要升序排序就使用大顶堆，反之使用小顶堆。原因是堆顶元素需要交换到序列尾部。

首先，实现堆排序需要解决两个问题：

1.如何由一个无序序列建成一个堆？

2.如何在输出堆顶元素之后，调整剩余元素成为一个新的堆？

第一个问题，可以直接使用线性数组来表示一个堆，由初始的无序序列建成一个就需要自底向上从一个非叶元素开始挨个调整成一个堆。

第二个问题，怎么调整成堆？首先将堆顶元素和最后一个元素交换。然后比较当前堆顶元素的左右孩子节点，因为除了当前的堆顶元素，左右孩子堆均满足条件，这时需要选择当前堆顶元素与左右孩子节点的较大者（大顶堆）交换，直至叶子节点。我们称这个自堆顶到叶子的调整成为筛选。

从一个无序序列建堆的过程就是一个反复筛选的过程。若将此序列看成是一个完全二叉树，则最后一个非终端节点是n/2取底个元素，有次筛选即可。举个例子：

49,38,65,97,76,13,27,49序列的堆排序建初始堆和调整的过程如下：

public static void heapSort(int[] arr)
	{
		if(arr==null||arr.length==0)
			return;
		
		//建立大顶堆
		for(int i=arr.length/2;i>=0;i--)
		{
			heapAdjust(arr,i,arr.length-1);
		}
		
		for(int i=arr.length-1;i>=0;i--)
		{
			swap(arr,0,i);
			heapAdjust(arr,0,i-1);
		}
	}

	private static void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
		
	}

	private static void heapAdjust(int[] arr, int start, int end) {
		int temp=arr[start];
		
		for(int i=2*start+1;i<=end;i*=2)
		{
			//左右孩子的节点分别是2*i+1，2*i+2
			//选择出左右孩子较小的下标
			if(i<end && arr[i]<arr[i+1])
			{
				i++;
			}
			if(temp>=arr[i])
			{
				break;//已经为大顶堆，保持稳定性
			}
			arr[start] = arr[i];//将节点上移
			start = i; //下一轮筛选
		}
		arr[start] = temp;//插入正确的位置
	}

归并排序采用了递归分治的思想，其思想是，先递归划分子问题，然后合并结果。把待排序列看成由两个有序的序列，然后合并两个子序列，然后把子序列看成由两个有序序列。。倒着看就是两两合并，然后四四合并。。最终形成有序序列。空间复杂度为O（n）,时间复杂度为O(logn)

实现代码：

public static void mSort(int[] arr,int left,int right)
    {
        if(left>=right) return;
        int mid =(left+right)/2;
        
        mSort(arr, left, mid);
        mSort(arr, mid+1, right);
        Merge(arr,left,mid,right);
    }

    private static void Merge(int[] arr, int left, int mid, int right) {
        int[] temp = new int[right-left+1];
        
        int i=left;
        int j= mid+1;
        int k=0;
        
        while(i<=mid && j<=right)
        {
            if(arr[i]<=arr[j])
                temp[k++]=arr[i++];
            else
            {
                temp[k++] = arr[j++];
            }
        }
        while(i<=mid)
        {
            temp[k++]=arr[i++];
        }
        while(j<=right)
        {
            temp[k++]=arr[j++];
        }
        
        for(int p=0;p<temp.length;p++)
        {
            arr[left+p]=temp[p];
        }
        
    }

最后

以上就是隐形乌冬面为你收集整理的面试中常问的排序算法的全部内容，希望文章能够帮你解决面试中常问的排序算法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。