排序也成排序算法(Sort Algorithm)，排序是將一組數(shù)據(jù)，依指定的順序進行排列的過程
排序的分類
內(nèi)部排序：指將需要處理的所有數(shù)據(jù)都加載到內(nèi)部存儲器中進行排序
外部排序法：數(shù)據(jù)量過大，無法全部加載到內(nèi)存中，需要借助外部存儲進行排序
度量一個程序(算法)執(zhí)行時間的兩種方法
1.事后統(tǒng)計的方法
這種方法可行，但是有兩個問題，一是要想對設(shè)計的算法的運行性能進行評測，需要實際運行該程序：二是所得時間的統(tǒng)計量依賴于計算機的硬件，軟件等環(huán)境因素，這種方式，要在同一臺計算機的相同狀態(tài)下運行，才能比較那個算法速度更快
2.事前估算的方法
通過分析某個算法的時間復(fù)雜度來判斷那個算法更優(yōu)
算法的時間復(fù)雜度
時間頻度：一個算法花費的時間與算法中語句的執(zhí)行次數(shù)成正比例，哪個算法中語句執(zhí)行次數(shù)多，他花費時間就多，一個算法中的語句執(zhí)行次數(shù)稱為語句頻度或時間頻度 . 記為:T(n)
統(tǒng)計時間頻度時：隨著n的變大，常數(shù)項，低次項，系數(shù)可以忽略
時間復(fù)雜度
1.一般情況下，算法中的操作語句的重復(fù)執(zhí)行次數(shù)是問題規(guī)模n的某個函數(shù)，用T(n)表示，若有某個輔助函數(shù)f(n)，使得當n趨近于無窮大時，T(n)/f(n)的極限值為不等于零的常數(shù)，則稱f(n)是T(n)的同數(shù)量級函數(shù)。記作T(n)=O(f(n))，稱O(f(n))為算法的漸進時間復(fù)雜度，簡稱時間復(fù)雜度
2.T(n)不同，但時間復(fù)雜度可能相同
3計算時間復(fù)雜度的方法
用常數(shù)1代替運行時間中的所有加法常數(shù) T(n)=n^2 7n 6 => T(n)=n^2 7n 1
修改后的運行次數(shù)函數(shù)中，只保留最高階項 T(n)=n^2 7n 1 => T(n)=n^2
去除最高階項的系數(shù) T(n)=n^2=> T(n)=n^2
常見的時間復(fù)雜度
1.常數(shù)階O(1) :無論代碼執(zhí)行多少行，只要是沒有循環(huán)等復(fù)雜結(jié)構(gòu)，那么這個代碼的時間復(fù)雜度就都是O(1)
2.對數(shù)階O(log2n) ：
//說明：在while循環(huán)里面，每次都將i乘以2，乘完之后，i距離n就越來越近了，假設(shè)循環(huán)x次之后，退出循環(huán)，也就是說2的x次方等于n，那么x=log2n也就是說當循環(huán)log2n次以后，這個代碼就結(jié)束了。因此這個代碼的時間復(fù)雜度為:O(log2n)//如果a的x次方等于N（a>0，且a不等于1），那么數(shù)x叫做以a為底N的對數(shù)（logarithm），記作x=logaN。其中，a叫做對數(shù)的底數(shù)，N叫做真數(shù)//這段代碼執(zhí)行l(wèi)og2^1024次public static void main(String[] args) { int count=0; int i=1; int n=1024; while(i<n) { i=i*2; count ; } //log2^1024=10 System.out.println(count);//10 }3.線性階O(n) ：for循環(huán)代碼執(zhí)行n遍，因此他消耗的時間是隨著n的變化而變化的
4線性對數(shù)階O(nlog2n) ：線性對數(shù)階O(nlogN)其實非常容易理解，將時間復(fù)雜度為O(logn)的代碼循環(huán)N遍的話，那么時間復(fù)雜度就是n*O(logN)
5.平方階O(n^2) :如果把O(n)的代碼在嵌套一遍，他的時間復(fù)雜度就是O(n^2),
//這段代碼其實就是嵌套了2層n循環(huán)，他的時間復(fù)雜度就是O(n*n)for(x=1;i<=n;x ) { for(x=1;i<=n;x ) { j=i; j ; } }6.立方階O(n^3) :相當于三層for循環(huán)
7.k次方階(n^K)
8.指數(shù)階O(2^n)
空間復(fù)雜度
類似于時間復(fù)雜度的討論，一個算法的空間復(fù)雜度定義為該算法鎖耗費的存儲空間，他也是問題規(guī)模n的函數(shù)
冒泡排序
每一次進行排序都會確定出一個最大值
package sort;import java.text.SimpleDateFormat;import java.util.Arrays;import java.util.Date;public class BubbleSort { public static void main(String[] args) { //int arr[] = {3,9,-1,10,-2}; //時間復(fù)雜度O(n^2) //測試冒泡排序的速度，要求排序80000個數(shù)字 int[] arr = new int[80000]; for(int i=0;i<arr.length;i ) { //每循環(huán)一次就添加一個元素 arr[i]=(int)(Math.random()*80000); } Date data1 = new Date(); System.out.println(data1); SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss"); String dateStr = sdf.format(data1); System.out.println("開始時間" dateStr); System.out.println("排序進行中........"); //對數(shù)組進行排序 bubbleSort(arr); Date data2 = new Date(); String dateStr2 = sdf.format(data2); System.out.println("開始時間" dateStr2); System.out.println("排序結(jié)束"); } public static void bubbleSort(int[] arr) { int temp = 0;//臨時變量 boolean b = false; for(int i=0;i<arr.length-1;i ) {//一共需要進行arr.length-1次排序 for(int j=0; j<arr.length-1-i;j ) { if(arr[j]>arr[j 1]) { b=true; temp=arr[j]; arr[j]=arr[j 1]; arr[j 1]=temp; } } //System.out.println("第" (i 1) "次冒泡。。。。。"); //System.out.println(Arrays.toString(arr)); if(!b) { break; }else { b=false;//重置為false，是因為已經(jīng)有進行過排序 } } }}//冒泡排序平均15秒選擇排序
每次排序都確定出一個最小值
package sort;import java.text.SimpleDateFormat;import java.util.Arrays;import java.util.Date;public class SelectSort { public static void main(String[] args) { int[] arr = new int[80000]; for(int i=0;i<arr.length;i ) { //每循環(huán)一次就添加一個元素 arr[i]=(int)(Math.random()*80000); } Date data1 = new Date(); SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss"); String dateStr = sdf.format(data1); System.out.println("開始時間" dateStr); System.out.println("排序進行中........"); selectSort(arr); Date data2 = new Date(); String dateStr2 = sdf.format(data2); System.out.println("開始時間" dateStr2); System.out.println("排序結(jié)束"); //System.out.println(Arrays.toString(arr)); } //選擇排序arr[0]=min public static void selectSort(int[] arr) { for(int i=0;i<arr.length-1;i ) { int minIndex = i;//假定最小索引為0 int min = arr[i];//假定最小值是arr數(shù)組的0索引 for(int j = 1 i;j<arr.length;j ) { if(min > arr[j]) { min=arr[j];//重置最小值 minIndex=j;//重置最小值得索引 } } if(minIndex !=i) {//表示minIndex沒有放生交換 arr[minIndex] = arr[i 0];//101賦值給索引3 arr[0 i] = min;//1賦值給索引0 } } } }//選擇排序平均3秒插入排序
插入式排序?qū)儆趦?nèi)部排序法，是對于欲排序的元素以插入的方式找尋該元素的適當位置，已達到排序的目的
插入排序的思想：就是把一個數(shù)組看成兩張表，一張表存放有序元素，一張表存放無序元素，有序表初始元素為arr[0],通過與arr[0]的比較來決定插入的位置，以此類推。
package sort;import java.text.SimpleDateFormat;import java.util.Arrays;import java.util.Date;public class InsertSort { public static void main(String[] args) { int[] arr = new int[80000]; for(int i=0;i<arr.length;i ) { //每循環(huán)一次就添加一個元素 arr[i]=(int)(Math.random()*80000); } Date data1 = new Date(); SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss"); String dateStr = sdf.format(data1); System.out.println("開始時間" dateStr); System.out.println("排序進行中........"); insertSort(arr); Date data2 = new Date(); String dateStr2 = sdf.format(data2); System.out.println("開始時間" dateStr2); System.out.println("排序結(jié)束"); //int arr[] = {3,9,-1,10,-2}; } public static void insertSort(int[] arr) { for(int i = 1;i < arr.length; i ) { int insertVal = arr[i]; int insertIndex = i-1;//i-1的意思是要把插入的數(shù)與前一個數(shù)比較 //insertIndex >=0 防止越界 //insertVal < arr[insertIndex]) while(insertIndex >=0 && insertVal < arr[insertIndex]) { arr[insertIndex 1] = arr[insertIndex];//往后移 insertIndex--;//繼續(xù)與前面的數(shù)比較 } if(insertIndex 1!=i) { arr[insertIndex 1] = insertVal; } } }}//平均時間5秒