排序算法排序也成排序算法(Sort Algorithm),，排序是將一組數(shù)據(jù)，依指定的順序進(jìn)行排列的過程 排序的分類 內(nèi)部排序：指將需要處理的所有數(shù)據(jù)都加載到內(nèi)部存儲(chǔ)器中進(jìn)行排序 外部排序法：數(shù)據(jù)量過大,，無法全部加載到內(nèi)存中,，需要借助外部存儲(chǔ)進(jìn)行排序 度量一個(gè)程序(算法)執(zhí)行時(shí)間的兩種方法 1.事后統(tǒng)計(jì)的方法 這種方法可行,，但是有兩個(gè)問題，一是要想對(duì)設(shè)計(jì)的算法的運(yùn)行性能進(jìn)行評(píng)測(cè),，需要實(shí)際運(yùn)行該程序：二是所得時(shí)間的統(tǒng)計(jì)量依賴于計(jì)算機(jī)的硬件,，軟件等環(huán)境因素，這種方式,，要在同一臺(tái)計(jì)算機(jī)的相同狀態(tài)下運(yùn)行,，才能比較那個(gè)算法速度更快 2.事前估算的方法 通過分析某個(gè)算法的時(shí)間復(fù)雜度來判斷那個(gè)算法更優(yōu) 算法的時(shí)間復(fù)雜度 時(shí)間頻度：一個(gè)算法花費(fèi)的時(shí)間與算法中語(yǔ)句的執(zhí)行次數(shù)成正比例，哪個(gè)算法中語(yǔ)句執(zhí)行次數(shù)多,，他花費(fèi)時(shí)間就多,，一個(gè)算法中的語(yǔ)句執(zhí)行次數(shù)稱為語(yǔ)句頻度或時(shí)間頻度 . 記為:T(n) 統(tǒng)計(jì)時(shí)間頻度時(shí)：隨著n的變大，常數(shù)項(xiàng),，低次項(xiàng),，系數(shù)可以忽略 時(shí)間復(fù)雜度 1.一般情況下，算法中的操作語(yǔ)句的重復(fù)執(zhí)行次數(shù)是問題規(guī)模n的某個(gè)函數(shù),，用T(n)表示,，若有某個(gè)輔助函數(shù)f(n)，使得當(dāng)n趨近于無窮大時(shí),，T(n)/f(n)的極限值為不等于零的常數(shù),，則稱f(n)是T(n)的同數(shù)量級(jí)函數(shù)。記作T(n)=O(f(n)),，稱O(f(n))為算法的漸進(jìn)時(shí)間復(fù)雜度,，簡(jiǎn)稱時(shí)間復(fù)雜度 2.T(n)不同，但時(shí)間復(fù)雜度可能相同 3計(jì)算時(shí)間復(fù)雜度的方法 用常數(shù)1代替運(yùn)行時(shí)間中的所有加法常數(shù) T(n)=n^2 7n 6 => T(n)=n^2 7n 1 修改后的運(yùn)行次數(shù)函數(shù)中,，只保留最高階項(xiàng) T(n)=n^2 7n 1 => T(n)=n^2 去除最高階項(xiàng)的系數(shù) T(n)=n^2=> T(n)=n^2
常見的時(shí)間復(fù)雜度 1.常數(shù)階O(1) :無論代碼執(zhí)行多少行,，只要是沒有循環(huán)等復(fù)雜結(jié)構(gòu)，那么這個(gè)代碼的時(shí)間復(fù)雜度就都是O(1) 2.對(duì)數(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次以后,，這個(gè)代碼就結(jié)束了。因此這個(gè)代碼的時(shí)間復(fù)雜度為:O(log2n)
//如果a的x次方等于N（a>0,，且a不等于1）,，那么數(shù)x叫做以a為底N的對(duì)數(shù)（logarithm），記作x=logaN。其中,，a叫做對(duì)數(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遍，因此他消耗的時(shí)間是隨著n的變化而變化的 4線性對(duì)數(shù)階O(nlog2n) ：線性對(duì)數(shù)階O(nlogN)其實(shí)非常容易理解,，將時(shí)間復(fù)雜度為O(logn)的代碼循環(huán)N遍的話,，那么時(shí)間復(fù)雜度就是n*O(logN) 5.平方階O(n^2) :如果把O(n)的代碼在嵌套一遍，他的時(shí)間復(fù)雜度就是O(n^2), //這段代碼其實(shí)就是嵌套了2層n循環(huán),，他的時(shí)間復(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ù)雜度 類似于時(shí)間復(fù)雜度的討論,，一個(gè)算法的空間復(fù)雜度定義為該算法鎖耗費(fèi)的存儲(chǔ)空間，他也是問題規(guī)模n的函數(shù) 冒泡排序 每一次進(jìn)行排序都會(huì)確定出一個(gè)最大值 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};
//時(shí)間復(fù)雜度O(n^2)
//測(cè)試冒泡排序的速度,，要求排序80000個(gè)數(shù)字
int[] arr = new int[80000];
for(int i=0;i<arr.length;i ) {
//每循環(huán)一次就添加一個(gè)元素
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("開始時(shí)間" dateStr);
System.out.println("排序進(jìn)行中........");
//對(duì)數(shù)組進(jìn)行排序
bubbleSort(arr);
Date data2 = new Date();
String dateStr2 = sdf.format(data2);
System.out.println("開始時(shí)間" dateStr2);
System.out.println("排序結(jié)束");
}
public static void bubbleSort(int[] arr) {
int temp = 0;//臨時(shí)變量
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,，是因?yàn)橐呀?jīng)有進(jìn)行過排序
}
}
}
}
//冒泡排序平均15秒
選擇排序 每次排序都確定出一個(gè)最小值 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)一次就添加一個(gè)元素
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("開始時(shí)間" dateStr);
System.out.println("排序進(jìn)行中........");
selectSort(arr);
Date data2 = new Date();
String dateStr2 = sdf.format(data2);
System.out.println("開始時(shí)間" 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)部排序法,，是對(duì)于欲排序的元素以插入的方式找尋該元素的適當(dāng)位置，已達(dá)到排序的目的 插入排序的思想：就是把一個(gè)數(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)一次就添加一個(gè)元素
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("開始時(shí)間" dateStr);
System.out.println("排序進(jìn)行中........");
insertSort(arr);
Date data2 = new Date();
String dateStr2 = sdf.format(data2);
System.out.println("開始時(shí)間" 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ù)與前一個(gè)數(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;
}
}
}
}
//平均時(shí)間5秒
來源：https://www./content-1-292301.html
|
