介绍

  1. 建立大顶堆
  2. 然后将堆的根节点取出(一般是与最后一个节点进行交换)
  3. 再将前length-1个数组重新建立大顶堆。不断重复

构建大顶堆图解

图是我用word画的,画的不好见谅

1.首先得到一个完全二叉树

Bigpile1

2.选中第i/2个数

Bigpile2

3.把此数与两个孩子作对比并将最大的数字放在此位置

Bigpile3

4.然后不断向前寻找直到顶部

Bigpile4Bigpile5Bigpile6Bigpile7Bigpile8Bigpile9

将根节点取出与最后一个数交换

Bigpile10

最后将前length-1个数重新构建大顶堆不断循环

代码

 
/***
	  * 堆排序O(n*lgn)
	  * @param data
	  * @param i
	  * @param j
	  */
	 public static void swap(int[] data, int i, int j) {  
	        if (i == j) {  
	            return;  
	        }  
	        data[i] = data[i] + data[j];  
	        data[j] = data[i] - data[j];  
	        data[i] = data[i] - data[j];  
	    }  
	  
	    public  int[] heapSort(int[] data) {  
	        for (int i = 0; i < data.length; i++) { createMaxdHeap(data, data.length - 1 - i); swap(data, 0, data.length - 1 - i); // print(data); } return data; } public static void createMaxdHeap(int[] data, int lastIndex) { for (int i = (lastIndex - 1) / 2; i >= 0; i--) {  
	            // 保存当前正在判断的节点  
	            int k = i;  
	            // 若当前节点的子节点存在  
	            while (2 * k + 1 <= lastIndex) {  
	                // biggerIndex总是记录较大节点的值,先赋值为当前判断节点的左子节点  
	                int biggerIndex = 2 * k + 1;  
	                if (biggerIndex < lastIndex) {  
	                    // 若右子节点存在,如果不存在此时biggerIndex应该等于 lastIndex  
	                    if (data[biggerIndex] < data[biggerIndex + 1]) {  
	                        // 若右子节点值比左子节点值大,则biggerIndex记录的是右子节点的值  
	                        biggerIndex++;  
	                    }  
	                }  
	                if (data[k] < data[biggerIndex]) {  
	                    // 若当前节点值比子节点最大值小,则交换2者得值,交换后将biggerIndex值赋值给k  
	                    swap(data, k, biggerIndex);  
	                    k = biggerIndex;  
	                } else {  
	                    break;  
	                }  
	            }  
	        }  
	    }  

介绍

今天呢,介绍下使用快排的思想求第k个小的数。

  • 首先选中一个数字将数组中比此数字小的数字放在左边大的数字放在右边,并返回这个数字是数组中的第几位。
  • 如果选中数字的位数比我们k大,则在此数字左边的序列中寻找k,否则在右边寻找,直到找到那个数字。
  • 如果不存在返回-1

程序代码

/***
	 * 求第k个小的数
	 * @param arr
	 * @param st
	 * @param end
	 * @param k
	 * @return
	 */
	public int findk(int arr[],int st,int end,int k){
		if(k<0||st+k-1>end)
			return -1;//不存在第K小数  
	    if(st==end)
	    	return st;//只有一个元素  
	    int q = partition(arr,st,end);//这是枢轴的下标,我们需要知道它在[st..end]中是第几个   
	    int i = q-st+1;//枢轴是第i小数  
	    if(i==k)return i;//找到  
	    else if(i>k)return findk(arr,st,q-1,k);//如果第K小数小于第i小数,则应该在枢轴的左边继续找  
	    else return findk(arr,q+1,end,k-i);
	}
	/***
	 * 
	 * @param a
	 * @param p
	 * @param r
	 * @return
	 */
	 public int partition(int a[],int p,int r){
		 int x=a[r];
		 int tmp;
		 int middle=p;
		 for(int j=p;j            

介绍

归并排序采用的是分治法的思路。

使用递归将数组变成一个一个单一的数字,然后在不断合并。

合并的时候两个数组首先比较第一个那个比较小就放在合并后的数组中的第一个,然后+1继续比较下一个直到有一方已经结束,然后将另一方剩下的数字放入到合并后的数组。

如图所示(图摘自网络)

guibing

/***
	 * 归并排序(排序)O(n log n)
	 * @param nums
	 * @param low
	 * @param mid
	 * @param high
	 */
	 public  void merge(int[] nums, int low, int mid, int high) {  
	        int[] temp = new int[high - low + 1];  
	        int i = low;// 左指针  
	        int j = mid + 1;// 右指针  
	        int k = 0;  
	  
	        // 把较小的数先移到新数组中  
	        while (i <= mid && j <= high) {  
	            if (nums[i] < nums[j]) {  
	                temp[k++] = nums[i++];  
	            } else {  
	                temp[k++] = nums[j++];  
	            }  
	        }  
	  
	        // 把左边剩余的数移入数组  
	        while (i <= mid) {  
	            temp[k++] = nums[i++];  
	        }  
	  
	        // 把右边边剩余的数移入数组  
	        while (j <= high) {  
	            temp[k++] = nums[j++];  
	        }  
	  
	        // 把新数组中的数覆盖nums数组  
	        for (int k2 = 0; k2 < temp.length; k2++) {  
	            nums[k2 + low] = temp[k2];  
	        }  
	    }  
	/***
	 * 归并排序(递归)
	 * @param nums
	 * @param low
	 * @param high
	 * @return
	 */
	   public  int[] sort(int[] nums, int low, int high) {  
	        int mid = (low + high) / 2;  
	        if (low < high) {  
	            // 左边  
	            sort(nums, low, mid);  
	            // 右边  
	            sort(nums, mid + 1, high);  
	            // 左右归并  
	            merge(nums, low, mid, high);  
	        }  
	        return nums;  
	    } 

插入排序介绍

最坏时间复杂度O(N^2)

把待排序的纪录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的纪录插入完为止,得到一个新的有序序列。

从第二个数开始与第一个数进行比较,如果比第一个数小就把第一个数向后移,最后将那个数插入进有序的排序。

下面是排序算法

public  int[] InsertSort(int[] arr)
	{
	    int i, j;
	    int n = arr.length;
	    int key;
	 
	    //假定第一个元素被放到了正确的位置上
	    //这样,仅需遍历1 - n-1
	    for (i = 1; i < n; i++)
	    {
	        j = i;
	        key = arr[i];
	 
	        while (j > 0 && key < arr[j - 1])
	        {
	            arr[j] = arr[j - 1];
	            j--;
	        }
	 
	        arr[j] = key;
	    }
	    return arr;
	}

算法介绍

  • 设置两个变量i、j,排序开始的时候:i=0,j=N-1;
  • 以第一个数组元素作为关键数据,赋值给key,即key=A[0];
  • 从j开始向前搜索,即由后开始向前搜索(j--),找到第一个小于key的值A[j],将A[j]和A[i]互换;
  • 从i开始向后搜索,即由前开始向后搜索(i++),找到第一个大于key的A[i],将A[i]和A[j]互换。
  • 重复第3、4步,直到i=j; (3,4步中,没找到符合条件的值,即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值,使得j=j-1,i=i+1,直至找到为止。找到符合条件的值,进行交换的时候i, j指针位置不变。另外,i==j这一过程一定正好是i+或j-完成的时候,此时令循环结束)。

代码

 public int[] Kuaisort(int[] a,int low,int high){
         int start = low;
         int end = high;
         int key = a[low];
         
         
         while(end>start){
             //从后往前比较
             while(end>start&&a[end]>=key)  //如果没有比关键值小的,比较下一个,直到有比关键值小的交换位置,然后又从前往后比较
                 end--;
             if(a[end]<=key){ int temp = a[end]; a[end] = a[start]; a[start] = temp; } //从前往后比较 while(end>start&&a[start]<=key)//如果没有比关键值大的,比较下一个,直到有比关键值大的交换位置 start++; if(a[start]>=key){
                 int temp = a[start];
                 a[start] = a[end];
                 a[end] = temp;
             }
         //此时第一次循环比较结束,关键值的位置已经确定了。左边的值都比关键值小,右边的值都比关键值大,但是两边的顺序还有可能是不一样的,进行下面的递归调用
         }
         //递归
         if(start>low) sort(a,low,start-1);//左边序列。第一个索引位置到关键值索引-1
         if(end<high) sort(a,end+1,high);//右边序列。从关键值索引+1到最后一个
         return a;
     }
介绍摘自百度百科