排序算法排序也成排序算法(Sort Algorithm)，排序是將一組數(shù)據(jù)，依指定的順序進(jìn)行排列的過程 排序的分類 內(nèi)部排序：指將需要處理的所有數(shù)據(jù)都加載到內(nèi)部存儲器中進(jìn)行排序 外部排序法：數(shù)據(jù)量過大，無法全部加載到內(nèi)存中，需要借助外部存儲進(jìn)行排序 度量一個程序(算法)執(zhí)行時間的兩種方法 1.事后統(tǒng)計的方法 這種方法可行，但是有兩個問題，一是要想對設(shè)計的算法的運行性能進(jìn)行評測，需要實際運行該程序：二是所得時間的統(tǒng)計量依賴于計算機(jī)的硬件，軟件等環(huán)境因素，這種方式，要在同一臺計算機(jī)的相同狀態(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)，使得當(dāng)n趨近于無窮大時，T(n)/f(n)的極限值為不等于零的常數(shù)，則稱f(n)是T(n)的同數(shù)量級函數(shù)。記作T(n)=O(f(n))，稱O(f(n))為算法的漸進(jì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也就是說當(dāng)循環(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) :相當(dāng)于三層for循環(huán) 7.k次方階(n^K) 8.指數(shù)階O(2^n) 空間復(fù)雜度 類似于時間復(fù)雜度的討論，一個算法的空間復(fù)雜度定義為該算法鎖耗費的存儲空間，他也是問題規(guī)模n的函數(shù) 冒泡排序 每一次進(jìn)行排序都會確定出一個最大值 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("排序進(jìn)行中........");
//對數(shù)組進(jìn)行排序
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 ) {//一共需要進(jìn)行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)有進(jìn)行過排序
}
}
}
}
//冒泡排序平均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("排序進(jìn)行中........");
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)部排序法，是對于欲排序的元素以插入的方式找尋該元素的適當(dāng)位置，已達(dá)到排序的目的 插入排序的思想：就是把一個數(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("排序進(jìn)行中........");
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秒
來源：https://www./content-1-292301.html
|
