1.選擇排序
基本思想:
- 選擇排序(
Selection sort
)是一種簡(jiǎn)單直觀(guān)的排序算法衔蹲。它的工作原理如下:首先在未排序序列中找到最小元素,存放到排序序列的起始位置;然后,再?gòu)氖S辔磁判蛟刂欣^續(xù)尋找最小元 素,然后放到排序序列末尾便贵。以此類(lèi)推,直到所有元素均排序完畢。
實(shí)現(xiàn)步驟
- 第一趟排序在所有待排序的n個(gè)記錄中選出關(guān)鍵字最小的記錄,將它與數(shù)據(jù)表中的第一個(gè)記錄交換位置,使關(guān)鍵字最小的記錄處于數(shù)據(jù)表的最前端;
- 第二趟在剩下的n-1個(gè)記錄中再選出關(guān)鍵字最 小的記錄,將其與數(shù)據(jù)表中的第二個(gè)記錄交換位置,使關(guān)鍵字次小的記錄處于數(shù)據(jù)表的第二個(gè)位置;
- 重復(fù)這樣的操作,依次選出數(shù)據(jù)表中關(guān)鍵字第三小、第四小...的元素,將它們分別換到數(shù)據(jù)表的第三佳遂、第四...個(gè)位置上寥袭。
- 排序共進(jìn)行n-1趟,最終可實(shí)現(xiàn)數(shù)據(jù)表的升序排列路捧。
示例:
// 已知一個(gè)無(wú)序的數(shù)組,要求對(duì)數(shù)組進(jìn)行排序
int nums[8] = {99, 12, 88, 34, 5, 44, 12, 100};
int length = sizeof(nums) / sizeof(nums[0]);
for (int i = 0; i < length; i++) {
printf("nums[%i] = %i\n", i, nums[i]);
}
for (int i = 0; i < length - 1; i++) {
for (int j = i+1; j < length; j++) {
// printf("*");
// printf("i = %i, j = %i\n", i, j);
if (nums[i] > nums[j]) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
}
printf("-------排序結(jié)束-------\n");
for (int i = 0; i < length; i++) {
printf("nums[%i] = %i\n", i, nums[i]);
}
2.冒泡排序
基本思想
冒泡排序(
Bubble Sort
,臺(tái)灣譯為:泡沫排序或氣泡排序)是一種簡(jiǎn)單的排序算法传黄。它重復(fù) 地走訪(fǎng)過(guò)要排序的數(shù)列,一次比較兩個(gè)元素,如果他們的順序錯(cuò)誤就把他們交換過(guò)來(lái)杰扫。走訪(fǎng)數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換,也就是說(shuō)該數(shù)列已經(jīng)排序完成。這個(gè)算法的名字由來(lái) 是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端膘掰。冒泡排序 分為: 大數(shù)下沉 小數(shù)上浮
實(shí)現(xiàn)步驟
- 1)比較相鄰的元素章姓。如果第一個(gè)比第二個(gè)大,就交換他們兩個(gè)。
- 2)對(duì)每一對(duì)相鄰元素作同樣的工作,從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì)识埋。在這一點(diǎn),最后的元素應(yīng) 該會(huì)是最大的數(shù)凡伊。
- 3)針對(duì)所有的元素重復(fù)以上的步驟,除了最后一個(gè)。
- 4)持續(xù)每次對(duì)越來(lái)越少的元素重復(fù)上面的步驟,直到?jīng)]有任何一對(duì)數(shù)字需要比較
示例:
int nums[6] = {99, 12, 88, 34, 5, 7};
int length = sizeof(nums) / sizeof(nums[0]);
for (int i = 0; i < length; i++) {
printf("nums[%i] = %i\n", i, nums[i]);
}
for (int i = 0; i < length - 1; i++) {
for (int j = 0; j < length - 1 - i; j++) {
printf("*");
printf("%i == %i\n", j, j+1);
if (nums[j] > nums[j + 1]) {
int temp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = temp;
}
}
}
printf("------排序結(jié)束----\n");
for (int i = 0; i < length; i++) {
printf("nums[%i] = %i\n", i, nums[i]);
}
3.折半查找
基本思想
- 在有序表中,取中間元素作為比較對(duì)象,若給定值與中間元素的要查找的數(shù)相等,則查找成功;若給定值小于中間元素的要查找的數(shù),則在中間元素的左半?yún)^(qū)繼續(xù)查找;
- 若給定值大于中間元素的要查找的數(shù),則在中間元素的右半?yún)^(qū)繼續(xù)查找窒舟。不斷重復(fù)上述查找過(guò)程,直到查找成功,或所查找的區(qū)域無(wú)數(shù)據(jù)元素,查找失敗
實(shí)現(xiàn)步驟
- 在有序表中,取中間元素作為比較對(duì)象,若給定值與中間元素的要查找的數(shù)相等,則查找成功;
- 若給定值小于中間元素的要查找的數(shù),則在中間元素的左半?yún)^(qū)繼續(xù)查找;
- 若給定值大于中間元素的要查找的數(shù),則在中間元素的右半?yún)^(qū)繼續(xù)查找系忙。不斷重復(fù)上述查找過(guò) 程,直到查找成功,或所查找的區(qū)域無(wú)數(shù)據(jù)元素,查找失敗。
示例:
#include <stdio.h>
#include <time.h>
int findKey(int nums[], int key, int length);
int findKey2(int nums[], int length, int key);
int findKey3(int nums[], int length, int key);
int main(int argc, const char * argv[]) {
// 現(xiàn)在已知一個(gè)有序的數(shù)組, 和一個(gè)key. 要求從數(shù)組中找到key對(duì)應(yīng)的索引的位置
// 對(duì)該方法進(jìn)行封裝, 要求找到就返回對(duì)應(yīng)的索引, 找不到就返回-1
int nums[500000] = {1, 3, 5, 7, 9, [499999] = 99};
int key = 99;
int length = sizeof(nums) / sizeof(nums[0]);
/*
// 消耗了多少1181毫秒
clock_t startTime = clock();
int index = findKey(nums, key, length);
clock_t endTime = clock();
printf("消耗了多少%lu毫秒\n", endTime - startTime);
printf("index = %i\n", index);
*/
// 消耗了多少1毫秒
clock_t startTime = clock();
// int index = findKey2(nums, length, key);
// 消耗了多少2毫秒
int index = findKey3(nums, length, key);
clock_t endTime = clock();
printf("消耗了多少%lu毫秒\n", endTime - startTime);
printf("index = %i\n", index);
return 0;
}
int findKey3(int nums[], int length, int key)
{
int min, max, mid;
min = 0;
max = length - 1;
// 只要還在我們的范圍內(nèi)就需要查找
while (min <= max) {
// 計(jì)算中間值
mid = (min + max) / 2;
if (key > nums[mid]) {
min = mid + 1;
}else if (key < nums[mid])
{
max = mid - 1;
}else
{
return mid;
}
}
return -1;
}
int findKey2(int nums[], int length, int key)
{
int min, max, mid;
min = 0;
max = length - 1;
mid = (min + max) / 2;
while (key != nums[mid]) {
// 判斷如果要找的值, 大于了取出的值, 那么min要改變
if (key > nums[mid]) {
min = mid + 1;
// 判斷如果要找的值, 小雨了取出的值, 那么max要改變
}else if (key < nums[mid])
{
max = mid - 1;
}
// 超出范圍, 數(shù)組中沒(méi)有需要查找的值
if (min > max) {
return -1;
}
// 每次改變完min和max都需要重新計(jì)算mid
mid = (min + max) / 2;
}
// printf("aaaaaa\n");
return mid;
}
int findKey(int nums[], int key, int length)
{
for (int i = 0; i < length; i++) {
if (nums[i] == key) {
// printf("%i\n", i);
return i;
}
}
return -1;
}
附:排序和冒泡方法封裝
// 冒泡排序
void bubbleSort(int nums[], int length)
{
for (int i = 0; i < length - 1; i++) {
for (int j = 0; j < length - 1 - i; j++) {
if (nums[j] > nums[j + 1]) {
swap(nums, j, j+1);
}
}
}
}
// 選擇排序
void selectSort(int nums[], int length)
{
for (int i = 0; i < length - 1; i++) {
for (int j = i+1; j < length; j++) {
if (nums[i] > nums[j]) {
swap(nums, i, j);
}
}
}
}
// 交換兩個(gè)數(shù)的值
void swap(int nums[], int i, int j)
{
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}