掌握常見的內部排序方法（插入排序，冒泡排序，選擇排序，快速排序，堆排序，希爾排序，歸并排序，基數排序等）。數組高級以及Arrays(掌握)

排序方法		空間復雜度	時間復雜度	穩定性
插入排序	直接插入排序	O（1）	平均O（n2）最壞O（n2）最好O（n）	穩定
	折半插入排序	O（1）	平均O（nlogn）最壞O（n2）	穩定
	希爾排序	O（1）	平均O（n2）	不穩定
交換排序	?????????? 冒泡排序	O（1）	平均O（n2）最壞O（n2）最好O（n）	穩定
	?????????? 快速排序	平均O（nlogn）最壞O（n）	平均O（nlogn）最壞O（n2）平均O（nlogn）	不穩定
選 擇 排 序	?????????? 簡單選擇排序	O（1）	始終O（n2）	不穩定
	?????????? 堆排序	O（1）	平均O（nlogn）建堆O（n）調整O（logn）	不穩定
	歸并排序	O（n）	O（nlogn）	穩定
	基數排序	O（d(n+r)）	O（d(n+r)）	穩定

(1)排序 A:冒泡排序???? 相鄰元素兩兩比較，大的往后放，第一次完畢，最大值出現在了最大索引處。同理，其他的元素就可以排好。???????????????? public static void bubbleSort(int[] arr) {?????????for(int x=0; x<arr.length-1; x++) {?????????? for(int y=0; y<arr.length-1-x; y++) {??????????????if(arr[y] > arr[y+1]) {???????????????int temp = arr[y];??????????????? arr[y] = arr[y+1];?????????????? arr[y+1] = temp;?????????????????? }??????????????? }????????????? }?????????? }????????? B:選擇排序?????????? 把0索引的元素，和索引1以后的元素都進行比較，第一次完畢，最小值出現在了0索引。同理，其他的元素就可以排好。?????????????????public static void selectSort(int[] arr) {?????????? for(int x=0; x<arr.length-1; x++) {???????????? for(int y=x+1; y<arr.length; y++) {????????????????? if(arr[y] < arr[x]) {??????????????????? int temp = arr[x];??????????????????? arr[x] = arr[y];????????????????????arr[y] = temp;???????????????????? }???????????????? }????????????? }?????????? } C.插入排序算法:public static void insertSort(int[] arr) {????? for (int i = 1; i < arr.length; i++) {????????? if(arr[i]<arr[i-1]){???????? ? arr[0]=arr[i];????????? for(int j=i-1;arr[0]<arr[j];j--)//只要arr[i]大的都后移，找到arr[i]合適的插入位置?????????? arr[j+1]=arr[j];??????? arr[j+1]=arr[0];??????????? }??????? }??? }D希爾排序： /* * 希爾排序：先取一個小于n的整數d1作為第一個增量， * 把文件的全部記錄分成（n除以d1）個組。所有距離為d1的倍數的記錄放在同一個組中。 * 先在各組內進行直接插入排序；然后，取第二個增量d2<d1重復上述的分組和排序， * 直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有記錄放在同一組中進行直接插入排序為止。 */public class ShellSort { public static void sort(int[] data) { for (int i = data.length / 2; i > 2; i /= 2) {//設置增量 for (int j = 0; j < i; j++) { insertSort(data, j, i); } } insertSort(data, 0, 1);}private static void insertSort(int[] data, int start, int inc) { for (int i = start + inc; i < data.length; i += inc) { for (int j = i; (j >= inc) && (data[j] < data[j - inc]); j -= inc){ SortTest.swap(data, j, j - inc); } } }} E.快速排序：Void Quicksort(int A[],int low,int high){? If(low<high){????? Int pivotpos= partion(A, low ,high);//獲取樞軸數位置????? Quicksort(A,? low,pivotpos-1); Quicksort(A,pivotpos-1,high)}}Int partion(int A[],int low ,int high){?? Int pivot=Alow];? While(low<high){ While(low<high&&A[high]>=pivot)? high--;//從樞軸小的左移?????? A[low]=A[high]; While(low<high&&A[low] <=pivot) low++;//從樞軸大的右移????? A[high] =A[low]; ?A[low]=pivot;???? //樞軸最后存放的位置? ?return low;?? }}F:歸并排序：public?static?int[] sort(int[] a,int?low,int?high){????????int?mid = (low+high)/2;????????if(low<high){????????????sort(a,low,mid);//分成兩個子序列，分別遞歸排序????????????sort(a,mid+1,high);????????????//左右歸并????????????merge(a,low,mid,high);????????}????????return?a;????}//將兩個有序表合并成一個有序表???public?static?void?merge(int[] a,?int?low,?int?mid,?int?high) {????????int[] temp =?new?int[high-low+1];//定義一個數組????????int?i= low;????????int?j = mid+1;????????int?k=0;????????//?把較小的數先移到新數組中????????while(i<=mid && j<=high){????????????if(a[i]<a[j]){???????????????temp[k++] = a[i++];????????????}else{???????????????temp[k++] = a[j++];????????????}????????}????????//?把左邊剩余的數移入數組?????????while(i<=mid){????????????temp[k++] = a[i++];????????}????????//?把右邊邊剩余的數移入數組????????while(j<=high){????????????temp[k++] = a[j++];????????}????????//?把新數組中的數覆蓋nums數組????????for(int?x=0;x<temp.length;x++){??????????a[x+low] = temp[x];//原數組從low開始的????????}????}?G:堆排序//構建大根堆：將array看成完全二叉樹的順序存儲結構??? private int[] buildMaxHeap(int[] array){//從最后一個節點array.length-1的父節點（array.length-1）/2開始，直到根節點0，反復調整堆???????? for(int i=(array.length-1)/2;i>=0;i--){????????????? adjustDownToUp(array, i,array.length);????????? }????????? return array;????? }?????//將元素array[k]自下往上逐步調整樹形結構???? private void adjustDownToUp(int[] array,int k,int length){???????? int temp = array[k];?????????? for(int i=2*k; i<length; i=2*i){??? //i為初始化為節點k的左孩子，沿節點較大的子節點向下調整???????????? if(i<length && array[i]<array[i+1]){? //取節點較大的子節點的下標???????????????? i++;?? //如果節點的右孩子>左孩子，則取右孩子節點的下標??????????? }???????????? if(temp>=array[i]){? //根節點 >=左右子女中關鍵字較大者，調整結束???????????????? break;???????????? }else{?? //根節點 <左右子女中關鍵字較大者? ???????????????array[k] = array[i];? //將左右子結點中較大值array[i]調整到雙親節點上??????????????? k = i; //【關鍵】修改k值，以便繼續向下調整???????????? }???????? }??????? array[k] = temp;? //被調整的結點的值放人最終位置??? }???//堆排序????? public int[] heapSort(int[] array){????????? array = buildMaxHeap(array); //初始建堆，array[0]為第一趟值最大的元素????????? for(int i=array.length-1;i>1;i--){????????????? int temp = array[0];? //將堆頂元素和堆低元素交換，即得到當前最大元素正確的排序位置????????????? array[0] = array[i];???????????? array[i] = temp;??????????? adjustDownToUp(array, 0,i-1);? //整理，將剩余的元素整理成堆???????? }???????? return array;??? }(2)查找????? A:基本查找?????????? 針對數組無序的情況???????????????????? public static int getIndex(int[] arr,int value) {????????????? int index = -1;?????????????????????????? for(int x=0; x<arr.length; x++) {????????????????? if(arr[x] == value) {???????????????????? index = x;???????????????????? break;????????????????? }????????????? }?????????????????????????? return index;?????????? }?????? B:二分查找(折半查找)?????????? 針對數組有序的情況(千萬不要先排序，在查找)???????????????????? public static int binarySearch(int[] arr,int value) {????????????? int min = 0;????????????? int max = arr.length-1;????????????? int mid = (min+max)/2;?????????????????????????? while(arr[mid] != value) {????????????????? if(arr[mid] > value) {???????????????????? max = mid - 1;????????????????? }else if(arr[mid] < value) {???????????????????? min = mid + 1;????????????????? }?????????????????????????? if(min > max) {???????????????????? return -1;????????????????? }???????????????????? mid = (min+max)/2;????????????? }???????????????????????? return mid;?????????? }?

轉載于:https://www.cnblogs.com/rqy0526/p/10954444.html

總結

以上是生活随笔為你收集整理的掌握常见的内部排序方法（插入排序，冒泡排序，选择排序，快速排序，堆排序，希尔排序，归并排序，基数排序等）...的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。