基本算法分類結(jié)構(gòu)
基本排序算法.png
參考鏈接
http://www.cnblogs.com/0201zcr/p/4764427.html
http://www.cnblogs.com/qqzy168/archive/2013/08/03/3219201.html
交換排序—冒泡排序
描述：
在排序數(shù)組Arrys中，對(duì)當(dāng)前還未排好順序的全部輸，自上而下對(duì)相鄰兩數(shù)進(jìn)行比較和調(diào)整。讓較大的數(shù)往下沉，較小往下沉。即：發(fā)現(xiàn)相鄰比較數(shù)順序不符合排序要求，交換位置。
步驟：
比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)。
1.遍歷數(shù)組起始位i，i到arrys.length-1
2.再次遍歷數(shù)組，j位置到arrys.length-1-i
3.條件判斷，交換位置操作
/**
* 冒泡升序
* 對(duì)每一對(duì)相鄰元素作同樣的工作，從開始第一對(duì)到結(jié)尾的最后一對(duì)。在這一點(diǎn)，最后的元素應(yīng)該會(huì)是最大的數(shù)。
* 針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)。
* 持續(xù)每次對(duì)越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較。
* @param arrys
* @return
*/
public Integer[] bubbleSortByAsc(Integer[] arrys){
Integer[] clone = arrys.clone();
for(int i=0;i<clone.length-1;i++){
for(int j=0;j<clone.length-1-i;j++){
if(clone[j]>clone[j+1]){
int temp=clone[j];
clone[j]=clone[j+1];
clone[j+1]=temp;
}
}
}
return clone;
}
/**
* 冒泡降序
* @param arrys
* @return
*/
public Integer[] bubbleSortByDesc(Integer[] arrys){
Integer[] clone = arrys.clone();
for(int i=0;i<clone.length-1;i++){
for(int j=0;j<clone.length-1-i;j++){
if(clone[j]>clone[j+1]){
int temp=clone[j];
clone[j]=clone[j+1];
clone[j+1]=temp;
}
}
}
return clone;
}
交換排序—快速排序
描述：
選擇一個(gè)基準(zhǔn)元素，通常以第一個(gè)或最后一個(gè)，通過一趟排序，將待排序列分成兩部分。一部分比基準(zhǔn)元素小，另一部分比基準(zhǔn)元素大或相等
/**
* 快速排序升序
*
* @param nums src
* @return result
*/
public Integer[] quickSortByAsc(Integer[] nums) {
Integer[] clone = nums.clone();
System.out.println("quick sort by Asc");
quickSortByAsc(clone, 0, clone.length - 1);
return clone;
}
public void quickSortByAsc(Integer[] nums, int low, int high) {
if (low < high) {
int middle = getMiddleAsc(nums, low, high);
quickSortByAsc(nums, low, middle - 1);
quickSortByAsc(nums, middle + 1, high);
}
}
/**
* 獲取中軸位置(Asc升序)
*
* @param nums src
* @param low low
* @param high high
* @return position
*/
private int getMiddleAsc(Integer[] nums, int low, int high) {
int middleNum = nums[low];//取第一次傳入的low位位中軸數(shù)
while (low < high) {
while (low < high && nums[high] >= middleNum) {//右邊high游標(biāo)不斷前移，如果當(dāng)前位置的數(shù)大于中軸上的數(shù)
high--;
}
nums[low] = nums[high];//小的移到左邊
while (low < high && nums[low] <= middleNum) {//左邊low游標(biāo)不斷后移，如果當(dāng)前l(fā)ow位置的數(shù)小于中軸上的數(shù)
low++;
}
nums[high] = nums[low];//大的移到右邊
}
nums[low] = middleNum;//將中軸數(shù)放到正確的位置上
return low;
}
/**
* 快速排序降序
*
* @param nums src
* @return result
*/
public Integer[] quickSortByDesc(Integer[] nums) {
Integer[] clone = nums.clone();
System.out.println("quick sort by desc:");
quickSortByDesc(clone, 0, clone.length - 1);
return clone;
}
private void quickSortByDesc(Integer[] nums, int low, int high) {
if (low < high) {
int middle = getMiddleDesc(nums, low, high);
quickSortByDesc(nums, low, middle - 1);//對(duì)中軸左邊繼續(xù)排序
quickSortByDesc(nums, middle + 1, high);//對(duì)中軸右邊繼續(xù)排序
}
}
/**
* 獲取中軸位置(Desc降序)
*
* @param nums src
* @param low low
* @param high high
* @return position
*/
private int getMiddleDesc(Integer[] nums, int low, int high) {
int middleNum = nums[low];//取第一次傳入的low位位中軸數(shù)
while (low < high) {
while (low < high && nums[high] <= middleNum) {//右邊high游標(biāo)不斷前移，如果當(dāng)前位置的數(shù)小于中軸上的數(shù)
high--;
}
nums[low] = nums[high];//大的數(shù)移到左邊
while (low < high && nums[low] >= middleNum) {//左邊low游標(biāo)不斷后移，如果當(dāng)前l(fā)ow位置的數(shù)大于中軸上的數(shù)
low++;
}
nums[high] = nums[low];//小的數(shù)移到右邊
}
nums[low] = middleNum;//將中軸數(shù)放到正確的位置上
return low;
}
插入排序——直接插入排序
描述：
在排序的數(shù)組中，假設(shè)前面n-1（n>=2）個(gè)數(shù)已經(jīng)排好順序，現(xiàn)在將第n個(gè)數(shù)插入到前面的有序數(shù)組中，使得這n個(gè)數(shù)也是排好順序。反復(fù)循環(huán)。直到排列完成。
/**
* 基本思想：每步將一個(gè)待排序的記錄，按其順序碼大小插入到
* 前面已經(jīng)排序的字序列的合適位置（從后向前找到合適位置后），
* 直到全部插入排序完為止。
*
* 從第一個(gè)元素開始，該元素可以認(rèn)為已經(jīng)被排序
* 取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描
* 如果該元素（已排序）大于新元素，將該元素移到下一位置
* 重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置
* 將新元素插入到該位置中
* 重復(fù)步驟2
* @param nums
*/
public Integer[] insertSortByAsc(Integer[] nums){
System.out.println("insert sort by Asc:");
Integer[] clone = nums.clone();
for(int i=0;i<clone.length;i++){
int temp=clone[i];//取出下個(gè)待插入排序的數(shù)
int j=0;//插入的位置標(biāo)記
for(j=i;j>0&&temp<clone[j-1];j--){//滿足待排序數(shù)小于前面的數(shù)條件，j--
clone[j]=clone[j-1];//整體后移一位
}
clone[j]=temp;
}
return clone;
}
/**
* 基本思想：每步將一個(gè)待排序的記錄，按其順序碼大小插入到
* 前面已經(jīng)排序的字序列的合適位置（從后向前找到合適位置后），
* 直到全部插入排序完為止。
*
* 從第一個(gè)元素開始，該元素可以認(rèn)為已經(jīng)被降序排序
* 取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描
* 如果該元素（已排序）小于新元素，將該元素移到下一位置
* 重復(fù)步驟3，直到找到已排序的元素大于或者等于新元素的位置
* 將新元素插入到該位置中
* 重復(fù)步驟2
* @param nums
*/
public Integer[] insertSortByDesc(Integer[] nums){
System.out.println("insert sort by Desc:");
Integer[] clone = nums.clone();
for(int i=0;i<clone.length;i++){
int temp=clone[i];//取出下個(gè)待插入排序的數(shù)
int j=0;//插入的位置標(biāo)記
for(j=i;j>0&&temp>clone[j-1];j--){//滿足待排序數(shù)大于前面的數(shù)條件，j--
clone[j]=clone[j-1];//整體后移一位
}
clone[j]=temp;
}
return clone;
}
插入排序——希爾排序
描述：將要排序的一組數(shù)按某個(gè)增量 d（n/2,n為要排序數(shù)的個(gè)數(shù)）分成若干組，每組中記錄的下標(biāo)相差 d.對(duì)每組中全部元素進(jìn)行直接插入排序，然后再用一個(gè)較小的增量（d/2）對(duì)它進(jìn)行分組，在每組中再進(jìn)行直接插入排序。當(dāng)增量減到 1 時(shí)，進(jìn)行直接插入排序后，排序完成。
/**
* 希爾排序升序
* 基本思想：
* 將數(shù)組拆分成d長(zhǎng)度的小數(shù)組，最開始d長(zhǎng)度為length/2
* 對(duì)小數(shù)組插入排序
* 再將d長(zhǎng)度縮小為d/2
* 重復(fù)操作，直到d=1
* @param nums src numbers
* @return result numbers
*/
public Integer[] shellSortAsc(Integer[] nums) {
System.out.println("shell sort by Asc:");
Integer[] clone = nums.clone();
for (int d = clone.length / 2; d >= 1; d /= 2) {//d每次縮小二分之一
for (int groupStarPosition = 0; groupStarPosition <= clone.length - d; groupStarPosition ++) {//分成d長(zhǎng)度的段
//對(duì)d長(zhǎng)度的每組數(shù)進(jìn)行插入排序,每組起始坐標(biāo)為groupStarPosition
for (int j = groupStarPosition; j < groupStarPosition+d; j++) {
int temp = clone[j];
int k = 0;
for (k = j; k > groupStarPosition && temp < clone[k - 1]; k--) {
clone[k] = clone[k - 1];
}
clone[k] = temp;
}
}
}
return clone;
}
/**
* 希爾排序升序
* 基本思想：
* 將數(shù)組拆分成d長(zhǎng)度的小數(shù)組，最開始d長(zhǎng)度為length/2
* 對(duì)小數(shù)組插入排序
* 再將d長(zhǎng)度縮小為d/2
* 重復(fù)操作，直到d=1
* @param nums src numbers
* @return result numbers
*/
public Integer[] shellSortByDesc(Integer[] nums) {
System.out.println("shell sort by Desc:");
Integer[] clone = nums.clone();
for (int d = clone.length / 2; d >= 1; d /= 2) {//d每次縮小二分之一
for (int groupStarPosition = 0; groupStarPosition <= clone.length - d; groupStarPosition ++) {//分成d長(zhǎng)度的段
//對(duì)d長(zhǎng)度的每組數(shù)進(jìn)行插入排序,每組起始坐標(biāo)為groupStarPosition
for (int j = groupStarPosition; j < groupStarPosition+d; j++) {
int temp = clone[j];
int k = 0;
for (k = j; k > groupStarPosition && temp > clone[k - 1]; k--) {
clone[k] = clone[k - 1];
}
clone[k] = temp;
}
}
}
return clone;
}
選擇排序——直接選擇排序
描述：排序的一組數(shù)中，選出最小的一個(gè)數(shù)與第一個(gè)位置的數(shù)交換；
然后在剩下的數(shù)當(dāng)中再找最小的與第二個(gè)位置的數(shù)交換，如此循環(huán)到倒數(shù)第二個(gè)數(shù)和最后一個(gè)數(shù)比較為止。
/**
* 選擇排序（升序）
* 每次選擇一個(gè)最小值排在有序數(shù)組的后面一位上
* 主要關(guān)心每次選擇的最小值的位置與值，再將此位置與數(shù)值交換
*
* @param nums src numbers
* @return result numbers
*/
public Integer[] selectSortByAsc(Integer[] nums) {
System.out.println("select sort by Asc:");
Integer[] clone = nums.clone();
int position = 0;//記錄本次選擇數(shù)的數(shù)組位置
int value = 0;//記錄本次選擇的值
for (int i = 0; i < clone.length; i++) {
value = clone[i];//初始值為clone[i]
for (int j = i; j < clone.length; j++) {
//如果發(fā)現(xiàn)有值比當(dāng)前選擇的值小，position記錄他在數(shù)組中的位置，更新value的值，進(jìn)行下次比較
if (clone[j] <= value) {
position = j;
value = clone[j];
}
}
//將此次選擇的最小值與clone[i]位置交換
int temp = clone[i];
clone[i] = value;
clone[position] = temp;
}
return clone;
}
/**
* 選擇排序(降序)
* 每次選擇一個(gè)最大值排在有序數(shù)組的后面一位上
* 主要關(guān)心每次選擇的最大值的位置與值，再將此位置與起始選擇位置交換
*
* @param nums src numbers
* @return result numbers
*/
public Integer[] selectSortByDesc(Integer[] nums) {
System.out.println("select sort by Desc:");
Integer[] clone = nums.clone();
int position = 0;//記錄本次選擇數(shù)的數(shù)組位置
int value = 0;//記錄本次選擇的值
for (int i = 0; i < clone.length; i++) {
value = clone[i];//初始值為clone[i]
for (int j = i; j < clone.length; j++) {
//如果發(fā)現(xiàn)有值比當(dāng)前選擇的值大，position記錄他在數(shù)組中的位置，更新value的值，進(jìn)行下次比較
if (clone[j] >= value) {
position = j;
value = clone[j];
}
}
//將此次選擇的最小值與clone[i]位置交換
int temp = clone[i];
clone[i] = value;
clone[position] = temp;
}
return clone;
}
選擇排序——堆排序(待續(xù))
歸并排序
歸并（Merge）排序法是將兩個(gè)（或兩個(gè)以上）有序表合并成一個(gè)新的有序表，即把待排序序列分為若干個(gè)子序列，每個(gè)子序列是有序的。然后再把有序子序列合并為整體有序序列。
/**
* 歸并排序升序
*
* @param nums src numbers
* @return result numbers
*/
public Integer[] mergeSortAsc(Integer[] nums) {
System.out.println("merge sort By Asc:");
Integer[] clone = nums.clone();
mergeSortAsc(clone, 0, clone.length - 1);
return clone;
}
/**
* low 到high 元素歸并
*
* @param nums src numbers
* @param low 歸并元素起始位置
* @param high 歸并元素結(jié)束位置
*/
public void mergeSortAsc(Integer[] nums, int low, int high) {
if (low < high) {
int middle = (low + high) / 2;
mergeSortAsc(nums, low, middle);//對(duì)左邊歸并排序
mergeSortAsc(nums, middle + 1, high);//對(duì)右邊歸并排序
mergeAsc(nums, low, middle, high);//歸并
}
}
/**
* 歸并操作，將有序的兩邊的子序列合并成整體有序的數(shù)
*
* @param nums 待排序數(shù)組
* @param low 待排的開始位置
* @param middle 待排中間位置
* @param high 待排結(jié)束位置
*/
public void mergeAsc(Integer[] nums, int low, int middle, int high) {
//輔助數(shù)組，用于存儲(chǔ)新排序好的數(shù)組
Integer[] temp = new Integer[high - low + 1];
//左指針
int left = low;
//右指針
int right = middle + 1;
//輔助數(shù)組的標(biāo)記
int k = 0;
// 把較小的數(shù)先移到新數(shù)組中
while (left <= middle && right <= high) {
if (nums[left] < nums[right]) {
temp[k] = nums[left];
left++;
k++;
} else {
temp[k] = nums[right];
right++;
k++;
}
}
// 把左邊剩余的數(shù)移入數(shù)組
while (left <= middle) {
temp[k++] = nums[left++];
}
// 把右邊剩余的數(shù)移入數(shù)組
while (right <= high) {
temp[k++] = nums[right++];
}
// 把新數(shù)組中的數(shù)覆蓋回到nums數(shù)組
for (int i = 0; i < temp.length; i++) {
nums[low + i] = temp[i];
}
}
/**
* 歸并排序（降序）
*
* @param nums src numbers
* @return result numbers
*/
public Integer[] mergeSortDesc(Integer[] nums) {
System.out.println("merge sort by Desc:");
Integer[] clone = nums.clone();
mergeSortDesc(clone, 0, clone.length - 1);
return clone;
}
/**
* low 到high 元素desc歸并
*
* @param nums src numbers
* @param low 歸并元素起始位置
* @param high 歸并元素結(jié)束位置
*/
public void mergeSortDesc(Integer[] nums, int low, int high) {
if (low < high) {
int middle = (low + high) / 2;
mergeSortDesc(nums, low, middle);
mergeSortDesc(nums, middle + 1, high);
mergeDesc(nums, low, middle, high);
}
}
/**
* 歸并操作，將有序的兩邊的子序列合并成整體有序的數(shù)
*
* @param nums 待排序數(shù)組
* @param low 待排的開始位置
* @param middle 待排中間位置
* @param high 待排結(jié)束位置
*/
public void mergeDesc(Integer[] nums, int low, int middle, int high) {
//輔助數(shù)組，用于存儲(chǔ)新排序好的數(shù)組
Integer[] temp = new Integer[high - low + 1];
//左指針
int left = low;
//右指針
int right = middle + 1;
//輔助數(shù)組的標(biāo)記
int k = 0;
// 把較大的數(shù)先移到新數(shù)組中
while (left <= middle && right <= high) {
if (nums[left] > nums[right]) {
temp[k] = nums[left];
left++;
k++;
} else {
temp[k] = nums[right];
right++;
k++;
}
}
// 把左邊剩余的數(shù)移入數(shù)組
while (left <= middle) {
temp[k++] = nums[left++];
}
// 把右邊剩余的數(shù)移入數(shù)組
while (right <= high) {
temp[k++] = nums[right++];
}
// 把新數(shù)組中的數(shù)覆蓋回到nums數(shù)組
for (int i = 0; i < temp.length; i++) {
nums[low + i] = temp[i];
}
}
