插入排序+希尔排序（插直希）

插入排序算法详解及实现

排序算法总结之插入排序

 

排序（二） 十分钟让你掌握插入排序

 

直接插入排序 

二分插入排序 

希尔排序

 

插入排序原理：

将一组数据分成两组，分别为有序组与待插入组。

每次从待插入组中取出一个元素，与有序组的元素进行比较，并找到合适的位置，将该元素插到有序组当中。就这样，每次插入一个元素，有序组增加，待插入组减少。直到待插入组元素个数为0。当然，插入过程中涉及到了元素的移动。

 

插入排序算法有种递归的思想在里面，它由N-1趟排序组成。初始时，只考虑数组下标0处的元素，只有一个元素，显然是有序的。

然后第一趟 对下标 1 处的元素进行排序，保证数组[0,1]上的元素有序；

第二趟 对下标 2 处的元素进行排序，保证数组[0,2]上的元素有序；

.....

.....

第N-1趟对下标 N-1 处的元素进行排序，保证数组[0,N-1]上的元素有序，也就是整个数组有序了。

它的递归思想就体现在：当对位置 i 处的元素进行排序时，[0,i-1]上的元素一定是已经有序的了。

 

  void InsertionSort(int *num,int n) 
  {
  	int i = 0;
  	int j = 0;
  	int tmp = 0;
  	for(i = 1;i<n;i++)
  	{
           tmp = num[i];//从待插入组取出第一个元素。 
	   j = i-1; //i-1即为有序组最后一个元素（与待插入元素相邻）的下标 
	    while(j>=0&&tmp<num[j])  //注意判断条件为两个，j>=0对其进行边界限制。第二个为插入判断条件 
	   {
	        num[j+1] = num[j];//若不是合适位置，有序组元素向后移动 
		 j--; 
	   }
	    num[j+1] = tmp;//找到合适位置，将元素插入。 
	}
  }
  int main() 
  {
  	int i = 0;
  	int num[8]={9,3,4,2,6,7,5,1};
  	InsertionSort(num,8); 
  	/*这个函数必须知道元素的个数，所以将元素个数传入。
	有心者可以在函数内部用sizeof求出元素个数 */
  	for(i=0;i<8;i++)
  	{
     	printf("%d ",num[i]);
	}
  	return 0;
  }

 

package com.test;

public class InsertSort {

	public static void printArray(int[] a){  
        for(int item : a){  
            System.out.print(item + " ");  
        }  
    }  
	
	
	public static void main(String[] args) {
		int[] arr={5,3,2,45,65,33,12};     
		sort(arr);
		printArray(arr);
	}
	
	
	public static void sort(int[] arr){
		
		//以第一个为已排序队列，后面所有数字为待排序队列
		for(int i=1;i<arr.length;i++){
			//从待插入组取出第一个元素
			int tmp = arr[i];
			
			int j = 0;
			for(j = i-1;j>=0;j--){
				
				//若待插入数字小于已排序队列最后一个数字，则将已排序队列最后一个数字往后移一位
				if(tmp < arr[j]){					
					arr[j+1] = arr[j];
				}else{
					//若待插入数字大于已排序队列最后一个数字，则直接跳出
					break;
				}
				
			}
			
			arr[j+1] = tmp;
		}
	}
}

  

二、希尔排序

图解排序算法(二)之希尔排序

。。。