小男孩‘自慰网亚洲一区二区,亚洲一级在线播放毛片,亚洲中文字幕av每天更新,黄aⅴ永久免费无码,91成人午夜在线精品,色网站免费在线观看,亚洲欧洲wwwww在线观看

搜索
分享

七大排序算法（冒泡，選擇，插入，二分法排序，希爾，快速，合并，堆排序）的java實(shí)現(xiàn)（14/8/3更新加入二分排序）

 醉人說夢(mèng) 2020-04-13

冒泡排序

思路：就是每次將最大或最小的元素放到數(shù)組的最后，so easy！時(shí)間復(fù)雜度為（O（n^2））
  1. public class BubbleSort {
  2. 	public static void bubbleSort(int[] a) {
  3. 		for (int j = 1; j < a.length; j++) {
  4. 			for (int i = 0; i < a.length - j; i++) {
  5. 				if (a[i] > a[i + 1]) {
  6. 					int temp = a[i];
  7. 					a[i] = a[i + 1];
  8. 					a[i + 1] = temp;
  9. 				}
  10. 			}
  11. 		}
  12. 	}
  13. 	public static void main(String[] args) {
  14. 		int a[] = { 5, 2, 45, 7, 2, 4, 2, 45, 7, 2, 4, 2, 45, 7, 2, 4, 23, 7, 2, 3, 0, 43, 23, 12, 4, 1, 15, 7,
  15. 				3, 8, 31 };
  16. 		bubbleSort(a);
  17. 		for(int i = 0; i < a.length; i++){
  18. 			System.out.print(a[i]+" ");
  19. 		}
  20. 	}
  21. }

選擇排序

思路：類似于冒泡，每次將后面最小的元素放在前面。時(shí)間復(fù)雜度為（（O（n^2）））
  1. public class SelectSort {
  2. 	public static void selectSort(int[] a) {
  3. 		int min;
  4. 		for (int i = 0; i < a.length - 1; i++) {
  5. 			min = i;
  6. 			for (int j = min + 1; j < a.length; j++) {
  7. 				if (a[min] > a[j]) {
  8. 					int temp = a[min];
  9. 					a[min] = a[j];
  10. 					a[j] = temp;
  11. 				}
  12. 			}
  13. 		}
  14. 	}
  16. 	public static void main(String[] args) {
  17. 		int a[] = { 5, 2, 45, 7, 2, 4, 2, 45, 7, 2, 4, 2, 45, 7, 2, 4, 23, 7,
  18. 				2, 3, 0, 43, 23, 12, 4, 1, 15, 7, 3, 8, 31 };
  19. 		selectSort(a);
  20. 		for (int i = 0; i < a.length; i++) {
  21. 			System.out.print(a[i] + " ");
  22. 		}
  23. 	}
  24. }

插入排序

思路：從第二個(gè)元素開始，和之前的已排好序的字?jǐn)?shù)組的元素比較，找到合適的位置，然后后面的元素向后移動(dòng)一位，再將該元素插入到前面合適的位置。時(shí)間復(fù)雜度為（O（n^2））
  1. public class InsertSort {
  2. 	public static void insertSort(int[] a) {
  3. 		for (int i = 1; i < a.length; i++) {
  4. 			int key = a[i];
  5. 			int j = i - 1;
  6. 			while (j >= 0 && a[j] > key) {
  7. 				a[j+1] = a[j];
  8. 				j--;
  9. 			}
  10. 			a[j+1] = key;
  11. 		}
  12. 	}
  14. 	public static void main(String[] args) {
  15. 		int a[] = { 5, 2, 45, 7, 2, 4, 2, 45, 7, 2, 4, 2, 45, 7, 2, 4, 23, 7,
  16. 				2, 3, 0, 43, 23, 12, 4, 1, 15, 7, 3, 8, 31 };
  17. 		insertSort(a);
  18. 		for (int i = 0; i < a.length; i++) {
  19. 			System.out.print(a[i] + " ");
  20. 		}
  21. 	}
  22. }

二分法排序

思路:插入排序的多此一舉，居然先用二分法查找插入位置（多此一舉），然后再所有插入位置（二分法查出來的）后面的元素全部后移，太蛋疼了，插入法直接邊找邊后移多容易啊，這個(gè)事蛋疼的做法，下午想了一下做出來。（14、08、3）
  1. package sort;
  3. public class BinarySort {
  4. 	public static int binarySerch(int[] arr, int start, int end, int value) {
  5. 		int mid = -1;
  6. 		while (start <= end) {
  7. 			mid = (start + end) / 2;
  8. 			if (arr[mid] < value)
  9. 				start = mid + 1;
  10. 			else if (arr[mid] > value)
  11. 				end = mid - 1;
  12. 			else
  13. 				break;
  14. 		}
  15. 		if (arr[mid] < value)
  16. 			return mid + 1;
  17. 		else if (value < arr[mid])
  18. 			return mid;
  20. 		return mid + 1;
  22. 	}
  24. 	public static void binarySort(int[] arr, int start, int end) {
  25. 		for (int i = start + 1; i <= end; i++) {
  26. 			int value = arr[i];
  27. 			int insertLoc = binarySerch(arr, start, i - 1, value) ;
  28. 			for (int j = i; j > insertLoc; j--) {
  29. 				arr[j] = arr[j - 1];
  30. 			}
  31. 			arr[insertLoc] = value;
  32. 		}
  33. 	}
  35. 	public static void main(String[] args) {
  36. 		int[] arr = { 3, 5, 0, 8, 7, 9, 1, 2, 6, 4 };
  37. 		binarySort(arr, 0, arr.length - 1);
  38. 		for (int i = 0; i < arr.length; i++) {
  39. 			System.out.print(arr[i] + " ");
  40. 		}
  41. 	}
  42. }


希爾排序

思路：類似于插入排序，只是每次所取的步長為（數(shù)組的長度 /  2 / i）。時(shí)間復(fù)雜度為（n*log n）。
  1. public class ShellSort {
  2. 	public static void shellSort(int[] a) {
  3. 		for (int gap = a.length / 2; gap > 0; gap /= 2)
  4. 			for (int i = gap; i < a.length; i++) {
  5. 				int key = a[i];
  6. 				int j = i - gap;
  7. 				while (j >= 0 && a[j] > key) {
  8. 					a[j + gap] = a[j];
  9. 					j -= gap;
  10. 				}
  11. 				a[j + gap] = key;
  12. 			}
  14. 	}
  16. 	public static void main(String[] args) {
  17. 		int a[] = { 5, 2, 45, 7, 2, 4, 2, 45, 7, 2, 4, 2, 45, 7, 2, 4, 23, 7,
  18. 				2, 3, 0, 43, 23, 12, 4, 1, 15, 7, 3, 8, 31 };
  19. 		shellSort(a);
  20. 		for (int i = 0; i < a.length; i++) {
  21. 			System.out.print(a[i] + " ");
  22. 		}
  23. 	}
  24. }

快速排序

思路：關(guān)鍵在于求出partition（）函數(shù)。我給出了兩種方法：1、從前到后。2、從前到中間，從后到中間。時(shí)間復(fù)雜度為（n * log n）最壞情況為
OK！show your my codes！
  1. public class QuickSort {
  3. 	/*public static int partition(int[] a, int p, int r) {
  4. 		int x = a[r];
  5. 		int i = p - 1;
  6. 		for (int j = p; j < r; j++) {
  7. 			if (a[j] <= x) {//如果a[j]<x就將后面a[i]后面a[i+1](值大于x)與a[j](值<a[j])進(jìn)行交換
  8. 				i++;
  10. 				int temp = a[i];
  11. 				a[i] = a[j];
  12. 				a[j] = temp;
  14. 			}
  15. 		}
  16. 		i++;
  17. 		int temp = a[i];
  18. 		a[i] = a[r];
  19. 		a[r] = temp;
  20. 		return i;
  21. 	}*/
  23. 	public static int partition(int a[], int p, int r) {
  24. 		int x = a[p];
  25. 		int i = p;
  26. 		int j = r ;
  27. 		while (i < j) {
  28. 			while (a[j] >= x && i<j)
  29. 				j--;
  30. 			a[i] = a[j];//把小于X的那個(gè)數(shù)拿到前面的a【i】中
  31. 			while (a[i] <= x && i<j)
  32. 				i++;
  33. 			a[j] = a[i];//把大于X的那個(gè)數(shù)拿到后面的a【j】中
  34. 		}
  35. 		a[j] = x;//將X拿到分割處
  36. 		return j;
  37. 	}
  39. 	public static void quickSort(int[] a, int p, int r) {
  40. 		if (p < r) {
  41. 			int q = partition(a, p, r);
  42. 			quickSort(a, p, q-1);
  43. 			quickSort(a, q + 1, r);
  44. 		}
  45. 	}
  47. 	public static void main(String[] args) {
  48. 		int a[] = { 5, 2, 45, 7, 2, 4, 2, 45, 7, 2, 4, 2, 45, 7, 2, 4, 23, 7, 2, 3, 0, 43, 23, 12, 4, 1, 15, 7,
  49. 				3, 8, 31 };
  50. 		quickSort(a, 0, a.length-1);
  51. 		for (int i = 0; i < a.length; i++) {
  52. 			System.out.print(a[i] + " ");
  53. 		}
  55. 	}
  56. }

合并排序

思路：用分治的思想，將數(shù)組分至最小，再合并即可，不懂自己google吧！時(shí)間復(fù)雜度為（n * log n ）是一個(gè)穩(wěn)定的排序算法。
  1. public class MergeSort {
  2. 	public static void merge(int A[], int p, int q, int r) {
  3. 		int[] L = new int[q - p + 1];
  4. 		int[] R = new int[r - q];
  5. 		for (int i = p, j = 0; i <= q; i++, j++) {
  6. 			L[j] = A[i];
  7. 		}
  8. 		for (int i = q + 1, j = 0; i <= r; i++, j++) {
  9. 			R[j] = A[i];
  10. 		}
  11. 		int pos = p;
  12. 		int i = 0, j = 0;
  13. 		for (; i < L.length && j < R.length;) {
  14. 			if (L[i] <= R[j]) {
  15. 				A[pos++] = L[i++];
  16. 			} else {
  17. 				A[pos++] = R[j++];
  18. 			}
  19. 		}
  20. 		if (i < L.length) {
  21. 			for (; i < L.length;)
  22. 				A[pos++] = L[i++];
  23. 		} else if (j < R.length) {
  24. 			for (; j < R.length;)
  25. 				A[pos++] = R[j++];
  26. 		}
  27. 	}
  29. 	public static void mergeSort(int[] A, int p, int r) {
  30. 		if (p < r) {
  31. 			int q = (p + r) / 2;
  32. 			mergeSort(A, p, q);
  33. 			mergeSort(A, q + 1, r);
  34. 			merge(A, p, q, r);
  35. 		}
  36. 	}
  38. 	public static void main(String[] args) {
  39. 		int A[] = { 5, 2, 45, 7, 2, 4, 2, 45, 7, 2, 4, 2, 45, 7, 2, 4, 23, 7, 2, 3, 0, 43, 23, 12, 4, 1, 15, 7,
  40. 				3, 8, 31 };
  41. 		mergeSort(A, 0, A.length - 1);
  42. 		for (int i = 0; i < A.length; i++) {
  43. 			System.out.print(A[i] + " ");
  44. 		}
  45. 	}
  46. }

堆排序

思路：建立一個(gè)堆，大頂堆或者小頂堆都可以。每次將堆頂元素放到數(shù)組最后，然后堆的規(guī)模減小一個(gè)，再維持第一個(gè)元素的大頂堆性質(zhì)。時(shí)間復(fù)雜度為（n * log n）。
  1. public class HeapSort {
  2. 	//求雙親位置
  3. 	static int parent(int i) {
  4. 		return i / 2;
  5. 	}
  6. 	//求左孩子位置
  7. 	static int left(int i) {
  8. 		return 2 * i;
  9. 	}
  10. 	//求右孩子位置
  11. 	static int right(int i) {
  12. 		return 2 * i + 1;
  13. 	}
  14. 	//維持大頂堆的性質(zhì)
  15. 	static void maxHelpify(int[] A, int i) {
  16. 		int l = left(i);
  17. 		int r = right(i);
  18. 		int largest = 0;
  19. 		if (l <= A[0] && A[l] > A[i])
  20. 			largest = l;
  21. 		else
  22. 			largest = i;
  23. 		if (r <= A[0] && A[r] > A[largest])
  24. 			largest = r;
  25. 		if (largest != i) {
  26. 			int temp = A[largest];
  27. 			A[largest] = A[i];
  28. 			A[i] = temp;
  29. 			maxHelpify(A, largest);
  30. 		}
  31. 	}
  32. 	//建立大頂堆
  33. 	static void buildMaxHeap(int[] A){
  34. 		for(int i=(A.length-1)/2; i>0; i--){
  35. 			maxHelpify(A, i);
  36. 		}
  37. 	}
  38. 	//堆排序
  39. 	public static void heapSort(int[] A){
  40. 		buildMaxHeap(A);//建立大頂堆
  41. 		//每次把堆頂?shù)臄?shù)放到數(shù)組最后，然后把堆的大小減1，再次維持第一個(gè)數(shù)的大頂堆性質(zhì)
  42. 		for(int i = A.length - 1; i>=2; i--){
  43. 			int temp = A[1];
  44. 			A[1] = A[i];
  45. 			A[i] = temp;
  46. 			A[0]--;
  47. 			maxHelpify(A, 1);
  48. 		}
  49. 	}
  50. 	public static void main(String[] args) {
  51. 		int A[] = new int[3];
  52. 		A[0] = A.length-1;//a[0]存放堆的大小
  53. 		for(int i = 1; i < A.length; i++){
  54. 			A[i] = (int) (Math.random()*10);
  55. 		}
  56. 		heapSort(A);
  57. 		for (int i = 1; i < A.length; i++) {
  58. 			System.out.print(A[i] + " ");
  59. 		}
  60. 	}
  61. }


其他：還有一種計(jì)數(shù)排序。

比較簡單：就是將數(shù)組下標(biāo)作為元素的value,特殊情況下使用。如排序N個(gè)人的年齡就可以用計(jì)數(shù)排序。將年齡看作數(shù)組的下標(biāo)，定義一個(gè)大小為100的數(shù)組，將年齡與之比較，如果年齡==下標(biāo)就將，該下標(biāo)的value+1.時(shí)間復(fù)雜度為（N）。

    本站是提供個(gè)人知識(shí)管理的網(wǎng)絡(luò)存儲(chǔ)空間，所有內(nèi)容均由用戶發(fā)布，不代表本站觀點(diǎn)。請(qǐng)注意甄別內(nèi)容中的聯(lián)系方式、誘導(dǎo)購買等信息，謹(jǐn)防詐騙。如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請(qǐng)點(diǎn)擊一鍵舉報(bào)。
    轉(zhuǎn)藏 分享 獻(xiàn)花（0）

    0條評(píng)論

    發(fā)表

    請(qǐng)遵守用戶 評(píng)論公約

    類似文章 更多