Java数据结构与算法之排序

    排序从大体上来讲，做了两件事情：

    1、比較两个数据项；

    2、交换两个数据项。或复制当中一项

    一、冒泡排序

    大O表示法：交换次数和比較次数都为O(N*N)。

    算法原理：

1. 1、比較相邻的元素。假设第一个比第二个大，就交换他们两个。

2. 2、对每一对相邻元素作相同的工作，从開始第一对到结尾的最后一对。

   在这一点。最后的元素应该会是最大的数。

3. 3、针对全部的元素反复以上的步骤，除了最后一个。
4. 4、持续每次对越来越少的元素反复上面的步骤，直到没有不论什么一对数字须要比較。

/**
	 * 冒泡排序 demo
	 * 
	 */
	public void bubbleSort(){
		
		int array [] = {22,41,22,12,93,42,23,54,77};
		
		for (int i = 0; i < array.length-1; i++) {
			
			for (int j = 0; j < array.length-i-1; j++) {
				
				int temp = 0;
				
				if (array[j]<=array[j+1]) {
					
				}else {
					
					temp = array[j];
					
					array[j] = array[j+1];
					
					array[j+1] = temp;
					
				}
			}
		}
	}

    二、选择排序

    选择排序改进了冒泡排序，将必要的交换次数从O(N*N)降低到O(N)次。

不幸的是比較次数仍保持为O(N*N)。然而，选择排序仍然为大记录量的排序提出了一个很重要的改进，由于这些大量的记录须要在内存中移动，这就使交换时间和比較时间比起来。交换的时间显得更为重要。

    算法原理：

    对照数组中前一个元素跟后一个元素的大小，假设后面的元素比前面的元素小则用一个变量k来记住他的位置，接着第二次比較。前面“后一个元素”现变成了“前一个元素”。继续跟他的“后一个元素”进行比較假设后面的元素比他要小则用变量k记住它在数组中的位置(下标)。等到循环结束的时候，我们应该找到了最小的那个数的下标了。然后进行推断，假设这个元素的下标不是第一个元素的下标。就让第一个元素跟他交换一下值。这样就找到整个数组中最小的数了。然后找到数组中第二小的数。让他跟数组中第二个元素交换一下值，以此类推。

/******************************************************** 
    *函数名称：SelectionSort 
    *说明：    选择排序 
    *********************************************************/  
    void SelectionSort()  
    {  
    	int array [] = {3,1,2,2,1,4,7,9,2,4,10};
    	int out,in,min;
        for(out = 0; out < array.length - 1; out++)    //从第一个位置開始  
        {  
        	min = out;//确保已经排出最小数据放在最左边的情况下。从最小数据右边第一个開始比較
            for (in = out + 1; in < array.length; in++) {   //寻找最小的数据索引   从1開始循环
                if (array[in] <= array[min]) { 
                    min = in;
                }
            }
            int temp = array[out];  
            array[out] = array[min];
            array[min] = temp;
            System.out.print("第"+out+"次排序：");
            for (int i = 0; i < array.length; i++) {
				System.out.print(array[i]+"\t");
			}
            System.out.println("");
        }  
    }  

    三、插入排序

    在大多数情况下，插入排序算法是主要的排序算法中效率最高的一个，尽管插入排序算法仍然须要O(N*N)的时间。可是普通情况下，它要比冒泡排序快一倍，比选择排序还要快一点。

    预设：局部有序

    算法原理：

将n个元素的数列分为已有序和无序两个部分。例如以下所看到的：

{{a1}。{a2。a3，a4，…，an}}

{{a1⑴。a2⑴}，{a3⑴，a4⑴ …，an⑴}}

…

{{a1(n-1），a2(n-1) ，…},{an(n-1)}}

每次处理就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比較。找出插入位置，将该元素插入到有序数列的合适位置中。

如果在一个无序的数组中，要将该数组中的数按插入排序的方法从小到大排序。如果啊a[]={3,5,2,1,4};插入排序的思想就是比大小，满足条件交换位置。一開始会像冒泡排序一样，但会比冒泡多一步就是交换后（a[i]=a[i+1]后）原位置（a[i]）会继续和前面的数比較满足条件交换，直到a[i+1]前面的数组是有序的。

比方在第二次比較后数组变成a[]={2,3,5,1,4};

/**
     * 插入排序
     */
    public void insertSort(){
    	
    	int array [] = {3,1,2};
    	
    	int in,out;
    	
    	for (out = 1; out < array.length; out++) {
			
    		int temp = array[out];//temp作为暂时变量，存储被标记的队员
    		
    		in = out;
    		
    		while(in>0 && array[in-1] >=temp){
    			
    			array[in] = array[in-1];//队员右移一位
    			
    			--in;
    			
    		}
    		array[in] = temp;//插入被标记的队员
    		

		}
    	
    }

    四、对象排序

    compareTo方法，对象排序有点须要注意。排序原理是这种，首先依据你所选属性进行排序。假设两个属性值一样，则依照下一个属性排，假设属性还是一样。则接着下一个属性往下排，依此类推。

/**
     * 对象排序
     */
    public void objectSort(){
    	
    	Person person1 = new Person("zhang", "san", 24);
    	
    	Person person2 = new Person("li", "si", 21);
    	
    	Person person3 = new Person("wang", "wu", 28);
    	
    	Person [] person = {person1,person2,person3};
    	
    	int in,out;
    	
    	for (out = 1; out < person.length; out++) {
    		
    		Person temp = person[out];
    		
    		in = out;
    		
    		while(in>0 && person[in-1].getLastName().compareTo(temp.getLastName())>0){
    			
    			person[in] = person[in-1];
    			
    			--in;
    			
    		}
    		
    		person[in] = temp;
    		
    		  System.out.print("第"+out+"次排序：");
              for (int i = 0; i < person.length; i++) {
  				System.out.print(person[i].getLastName()+"\t");
  			}
              System.out.println("");
			
		}
    	
    }
    public static void main(String[] args) {
		new Sort().objectSort();
	}
}
class Person{
	
	private String lastName;
	
	private String firstName;
	
	private int age;
	
	public Person(String lastName,String firstName,int age){
		
		this.lastName = lastName;
		
		this.firstName = firstName;
		
		this.age = age;
		
	}
	public String getLastName(){
		
		return lastName;
	}
}