 一、冒泡排序 冒泡排序(Bubble Sort)，是一種計(jì)算機(jī)科學(xué)領(lǐng)域的較簡(jiǎn)單的排序算法。 它重復(fù)地走訪過要排序的元素列，依次比較兩個(gè)相鄰的元素，如果他們的順序(如從大到小、首字母從A到Z)錯(cuò)誤就把他們交換過來。走訪元素的工作是重復(fù)地進(jìn)行直到?jīng)]有相鄰元素需要交換，也就是說該元素列已經(jīng)排序完成。 代碼： #include <iostream>using namespace std;
template<typename T>//整數(shù)或浮點(diǎn)數(shù)皆可使用void bubble_sort(T arr[], int len)
{int i, j; T temp;for (i = 0; i < len - 1; i++)for (j = 0; j < len - 1 - i; j++)if (arr[j] > arr[j + 1])
{
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}int main()
{int arr[] = { 61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62 };int len = (int) sizeof(arr) / sizeof(*arr);
bubble_sort(arr, len);for (int i = 0; i < len; i++)
cout << arr[i] << ' ';
cout << endl;float arrf[] = { 17.5, 19.1, 0.6, 1.9, 10.5, 12.4, 3.8, 19.7, 1.5, 25.4, 28.6, 4.4, 23.8, 5.4 };
len = (int) sizeof(arrf) / sizeof(*arrf);
bubble_sort(arrf, len);for (int i = 0; i < len; i++)
cout << arrf[i] << ' ';return 0;
}二、快速排序 快速排序(Quicksort)是對(duì)冒泡排序的一種改進(jìn)。 快速排序的思想是：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。 代碼： #include <iostream>using namespace std;void Qsort(int arr[], int low, int high){if (high <= low) return;int i = low;int j = high + 1;int key = arr[low];while (true)
{/*從左向右找比key大的值*/while (arr[++i] < key)
{if (i == high){break;
}
}/*從右向左找比key小的值*/while (arr[--j] > key)
{if (j == low){break;
}
}if (i >= j) break;/*交換i,j對(duì)應(yīng)的值*/int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}/*中樞值與j對(duì)應(yīng)值交換*/int temp = arr[low];
arr[low] = arr[j];
arr[j] = temp;
Qsort(arr, low, j - 1);
Qsort(arr, j + 1, high);
}int main()
{int a[] = {57, 68, 59, 52, 72, 28, 96, 33, 24};
Qsort(a, 0, sizeof(a) / sizeof(a[0]) - 1); /*這里原文第三個(gè)參數(shù)要減1否則內(nèi)存越界*/for(int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
{
cout << a[i] << "";
}return 0;
}三、合(歸)并排序 歸并排序(MERGE-SORT)是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法(Divide and Conquer)的一個(gè)非常典型的應(yīng)用。 將已有序的子序列合并，得到完全有序的序列;即先使每個(gè)子序列有序，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表，稱為二路歸并。 代碼： #include<iostream>using namespace std;void merge(int *data, int start, int mid, int end, int *result)
{int i, j, k;
i = start;
j = mid + 1; //避免重復(fù)比較data[mid]k = 0;while (i <= mid && j <= end) //數(shù)組data[start,mid]與數(shù)組(mid,end]均沒有全部歸入數(shù)組result中去{if (data[i] <= data[j]) //如果data[i]小于等于data[j]result[k++] = data[i++]; //則將data[i]的值賦給result[k]，之后i,k各加一，表示后移一位elseresult[k++] = data[j++]; //否則，將data[j]的值賦給result[k]，j,k各加一}while (i <= mid) //表示數(shù)組data(mid,end]已經(jīng)全部歸入result數(shù)組中去了，而數(shù)組data[start,mid]還有剩余result[k++] = data[i++]; //將數(shù)組data[start,mid]剩下的值，逐一歸入數(shù)組resultwhile (j <= end) //表示數(shù)組data[start,mid]已經(jīng)全部歸入到result數(shù)組中去了，而數(shù)組(mid,high]還有剩余result[k++] = data[j++]; //將數(shù)組a[mid,high]剩下的值，逐一歸入數(shù)組resultfor (i = 0; i < k; i++) //將歸并后的數(shù)組的值逐一賦給數(shù)組data[start,end]data[start + i] = result[i]; //注意，應(yīng)從data[start+i]開始賦值}void merge_sort(int *data, int start, int end, int *result)
{if (start < end)
{int mid = start + (end-start) / 2; //避免溢出intmerge_sort(data, start, mid, result); //對(duì)左邊進(jìn)行排序merge_sort(data, mid + 1, end, result); //對(duì)右邊進(jìn)行排序merge(data, start, mid, end, result); //把排序好的數(shù)據(jù)合并}
}void amalgamation(int *data1, int *data2, int *result)
{for (int i = 0; i < 10; i++)
result[i] = data1[i];for (int i = 0; i < 10; i++)
result[i + 10] = data2[i];
}int main()
{int data1[10] = { 1,7,6,4,9,14,19,100,55,10 };int data2[10] = { 2,6,8,99,45,63,102,556,10,41 };int *result = new int[20];int *result1 = new int[20];
amalgamation(data1, data2, result);for (int i = 0; i < 20; ++i)
cout << result[i] << " ";
cout << endl;
merge_sort(result, 0, 19, result1);for (int i = 0; i < 20; ++i)
cout << result[i] << " ";delete[]result;delete[]result1;return 0;
}四、二分查找 代碼： int find(int x,int y,int m) //在[x,y]區(qū)間查找關(guān)鍵字等于m的元素下標(biāo){ int head,tail,mid;
head=x;tail=y;mid=((x+y)/2); //取中間元素下標(biāo)if(a[mid]==m) return mid; //如果中間元素值為m返回中間元素下標(biāo)midif(head>tail) return 0; //如果x>y，查找失敗，返回0if(m>a[mid]) //如果m比中間元素大，在后半?yún)^(qū)間查找，返回后半?yún)^(qū)間查找結(jié)果return find(mid+1,tail);else //如果m比中間元素小，在前半?yún)^(qū)間查找，返回后前區(qū)間查找結(jié)果return find(head,mid-1); |
|
|
