數(shù)據(jù)結(jié)構(gòu)和算法總結(jié)
一、排序算法
1.1听盖、排序分類(lèi)
1.內(nèi)部排序
指將需要處理的所有數(shù)據(jù)都加載到內(nèi)部存儲(chǔ)器（內(nèi)存）中進(jìn)行排序曲楚。
2.外部排序法
數(shù)據(jù)量過(guò)大，無(wú)法全部加載到內(nèi)存中，需要借助外部存儲(chǔ)進(jìn)行排序鹃操。
1.2韭寸、十大排序算法總結(jié)
1.3、冒泡排序
1.算法步驟
step1：比較相鄰的元素荆隘，如果第一個(gè)比第二個(gè)大恩伺，就交換兩個(gè)元素。
step2：對(duì)每一個(gè)相鄰元素同樣的工作椰拒，從開(kāi)始到結(jié)尾晶渠，最后一個(gè)元素是已經(jīng)排序好的元素。
step3：重復(fù)step1燃观。
2.代碼實(shí)現(xiàn)
public class BubbleSort {
public static void s(int[] arr) {
for (int i = 0; i < arr.length; i++) {
// arr.length-i 重復(fù)遍歷未排序的數(shù)列褒脯。
for (int j = 1; j < arr.length-i; j++) {
if (arr[j-1] > arr[j]) {
int temp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;
}
}
}
}
3.冒泡排序改進(jìn)
（1）設(shè)置一個(gè)標(biāo)志性pos，記錄每趟排序中最后一次交換的位置仪壮。由于pos位置之后的記錄均已排序憨颠，故進(jìn)行下一次排序掃描到pos位置即可。
（2）傳統(tǒng)冒泡排序中每一趟排序操作只能找到一個(gè)最大值或最小值积锅，可以利用再每趟排序中進(jìn)行正向和方向兩遍冒泡排序的方法一次可以得到兩個(gè)最終值（最大值和最小值）爽彤，從而使排序趟數(shù)幾乎減少一半。
1.4缚陷、快速排序
1.算法步驟
略
2.代碼實(shí)現(xiàn)
public class QuickSort {
public static void quickSrot(int[] arr, int low, int high) {
int i, j, stan;
if (low > high) {
return;
}
stan = arr[low];
i = low;
j = high;
while (i < j) {
while (i < j && stan <= arr[j]) {
j--;
}
while (i < j && stan >= arr[i]) {
i++;
}
// 滿(mǎn)足條件交換
if (i < j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// 當(dāng)i==j适篙，交換基準(zhǔn)位
arr[low] = arr[i];
arr[i] = stan;
// 遞歸調(diào)用小于基準(zhǔn)數(shù)部分。
quickSrot(arr, low, i-1);
// 遞歸調(diào)用大于基準(zhǔn)數(shù)部分箫爷。
quickSrot(arr, i + 1, high);
return;
}
public static void main(String[] args) {
int[] arr = {10, 7, 2, 4, 7, 62, 3, 4, 2, 1, 8, 9, 19};
QuickSort quickSort = new QuickSort();
// 注意high初始值
quickSort.quickSrot(arr, 0, arr.length-1);
for (int item : arr) {
System.out.println(item);
}
}
}
3.快速排序改進(jìn)
（1）選擇基準(zhǔn)元素的方式（a.固定基準(zhǔn)元嚷节。b.隨機(jī)基準(zhǔn)元。c.三數(shù)取中）
（2）當(dāng)原表有序直接使用插入排序和冒泡排序可以減少比較次數(shù)虎锚，時(shí)間復(fù)雜度O(n)
1.5硫痰、插入排序
1、算法步驟
step1：從第一個(gè)元素開(kāi)始窜护，該元素默認(rèn)已經(jīng)排序效斑。
step2：取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描柱徙。
step3：如果已排序中的元素大于新元素缓屠，已排序元素向下移動(dòng)一位；重復(fù)step3护侮，直到已排序的元素小于或等于新元素位置敌完。
step4：將元素插入到該位置；重復(fù)step2~step5
2羊初、代碼實(shí)現(xiàn)
public class InsertSort {
public static void s(int[] arr) {
int len = arr.length;
// 第一個(gè)元素默認(rèn)已排好序
for (int i = 1; i < len; i++) {
int preIndex = i - 1;
// 取出下一個(gè)元素滨溉，在已排序好的序列中從前向后掃描。
int current = arr[i];
while (preIndex >= 0) {
// 如果該元素大于前一個(gè)元素，該元素向后移動(dòng)
if (arr[preIndex] > current) {
arr[preIndex+1] = arr[preIndex];
}
preIndex--;
}
// 找到該元素小于或等于新元素的位置
arr[preIndex+1] = current;
}
}
}
二业踏、數(shù)組和鏈表
數(shù)組：固定長(zhǎng)度禽炬，內(nèi)存角度方便查找
從訪(fǎng)問(wèn)方式：數(shù)組利用下表索引方便訪(fǎng)問(wèn)涧卵；鏈表只能通過(guò)線(xiàn)性訪(fǎng)問(wèn)由前到后順序訪(fǎng)問(wèn)勤家。
一個(gè)單鏈表怎么判斷有沒(méi)有環(huán)？環(huán)的起點(diǎn)怎么找柳恐？ 如何找出環(huán)的連接點(diǎn)在哪里伐脖？帶環(huán)鏈表的長(zhǎng)度是多少？
1乐设、對(duì)于問(wèn)題1讼庇，使用追趕的方法，設(shè)定兩個(gè)指針slow近尚、fast蠕啄，從頭指針開(kāi)始，每次分別前進(jìn)1步戈锻、2步歼跟。如存在環(huán)，則兩者相遇格遭；如不存在環(huán)哈街，fast遇到NULL退出。 2拒迅、對(duì)于問(wèn)題2骚秦，記錄下問(wèn)題1的碰撞點(diǎn)p，slow璧微、fast從該點(diǎn)開(kāi)始作箍，再次碰撞所走過(guò)的操作數(shù)就是環(huán)的長(zhǎng)度s。 3前硫、問(wèn)題3：有定理：碰撞點(diǎn)p到連接點(diǎn)的距離=頭指針到連接點(diǎn)的距離胞得，因此，分別從碰撞點(diǎn)开瞭、頭指針開(kāi)始走懒震，相遇的那個(gè)點(diǎn)就是連接點(diǎn)。 該定理的證明可參考：http://fayaa.com/tiku/view/7/ 4嗤详、問(wèn)題3中已經(jīng)求出連接點(diǎn)距離頭指針的長(zhǎng)度个扰，加上問(wèn)題2中求出的環(huán)的長(zhǎng)度，二者之和就是帶環(huán)單鏈表的長(zhǎng)度
三葱色、圖
鄰接矩陣與鄰接表
鄰接矩陣表示法：在一個(gè)一維數(shù)組中存儲(chǔ)所有的點(diǎn)递宅，在一個(gè)二維數(shù)組中存儲(chǔ)頂點(diǎn)之間的邊的權(quán)值
鄰接表表示法：圖中頂點(diǎn)用一個(gè)一維數(shù)組存儲(chǔ)，圖中每個(gè)頂點(diǎn)vi的所有鄰接點(diǎn)構(gòu)成單鏈表
四、哈希表
hashmap實(shí)現(xiàn)
解決哈希沖突的方法
1办龄、線(xiàn)性探測(cè)法 2烘绽、平方探測(cè)法 3、偽隨機(jī)數(shù)序列法 4俐填、拉鏈法
五安接、棧區(qū)、堆區(qū)和隊(duì)列
棧：限定只能在表的一端進(jìn)行插入和刪除操作的線(xiàn)性表英融。
隊(duì)列：限定只能在表的一端插入和在另一端進(jìn)行刪除盏檐。
