學習目錄：

　　選擇排序
　　冒泡排序
　　插入排序
　　歸并排序
　　二分法
　　異或運算

詳細決議后期會補上，目前先更新代碼塊

選擇排序（時間復雜度，O(N²) ）

 1 void selectSort(int array[], int len)
 2 {
 3     if (array == NULL || len < 2)
 4     {
 5         return;
 6     }
 7     for (int i = 0; i < len - 1; i++)
 8     {
 9         int minIndex = i;
10         for (int j = i + 1; j < len; j++)
11         {
12             if (array[j] < array[minIndex])
13             {
14                 Swap(array, minIndex, j);
15             }
16         }
17     }
18 }

冒泡排序（時間復雜度，O(N²) ）

 1 void BubbleSort(int array[], int len)
 2 {
 3     if (array == NULL || len < 2)
 4     {
 5         return;
 6     }
 7     for (int i = len - 1; i > 0; i--)
 8     {
 9         for (int j = 0; j < i; j++)
10         {
11             if (array[j] > array[j + 1])
12             {
13                 Swap(array, i, j);
14             }
15         }
16     }
17 }

插入排序（時間復雜度，最優O(N)，最差O(N²) ）

 1 void insertSort(int array[], int len)
 2 {
 3     if (array == NULL || len < 2)
 4     {
 5         return;
 6     }
 7     for (int i = 1; i < len; i++)
 8     {
 9         for (int j = i - 1; j >= 0 && array[j] > array[j + 1]; j--)
10         {
11             Swap(array, j, j + 1);
12         }
13     }
14 }

歸并排序（時間復雜度，O(N*logN) ）

 1 void merge(int array[], int L, int M, int R)
 2 {
 3     vector<int>help;
 4     int p1 = L;
 5     int p2 = M + 1;
 6     while (p1 <= M && p2 <= R)
 7     {
 8         help.push_back(array[p1] <= array[p2] ? array[p1++] : array[p2++]);
 9     }
10     while (p1 <= M)
11     {
12         help.push_back(array[p1++]);
13     }
14     while (p2 <= R)
15     {
16         help.push_back(array[p2++]);
17     }
18     for (int i = 0; i < help.size(); i++)
19     {
20         array[L + i] = help.at(i);
21     }
22 }
23 
24 void mergeSort(int array[], int L, int R)
25 {
26     if (L == R)
27     {
28         return;
29     }
30     int mid = L + ((R - L) >> 1);
31     mergeSort(array, L, mid);
32     mergeSort(array, mid + 1, R);
33     merge(array, L, mid, R);
34 }
35 
36 void mergeSort(int array[], int len)
37 {
38     if (array == NULL || len < 2)
39     {
40         return;
41     }
42     mergeSort(array, 0, len - 1);
43 }

歸并排序例題：

題目：小和問題

在一個陣列中，每一個數左邊比當前數小的和累加起來，叫做這個數的小和，

 1 int merge(int array[], int L, int R)
 2 {
 3     vector<int>help(R - L + 1);
 4     int M = L + ((R - L) >> 1);
 5     int res = 0;
 6     int p1 = L;
 7     int p2 = M + 1;
 8 
 9     while (p1 <= M&&p2 <= R)
10     {
11         res += array[p1] < array[p2] ? (R - L + 1)*array[p1] : 0;
12         help.push_back(array[p1] < array[p2] ? array[p1++] : array[p2++]);
13     }
14     while (p1 <= M)
15     {
16         help.push_back(array[p1++]);
17     }
18     while (p2 <= M)
19     {
20         help.push_back(array[p2++]);
21     }
22     return res;
23     
24 }
25 
26 int mergeSort(int array[], int L, int R)
27 {
28     if (L == R)
29     {
30         return 0;
31     }
32     int M = L + ((R - L) >> 1);
33     return merge(array, L, M) + merge(array, M + 1, R) + merge(array, L, R);
34 }
35 
36 int smallSum(int array[], int len)
37 {
38     if (array == NULL || len < 2)
39     {
40         return 0;
41     }
42     mergeSort(array, 0, len - 1);
43 }

二分法（時間復雜度，O(logN) ）

注：不一定是有序才能二分，例如區域最小值問題

 1 bool binarySort(int array[], int len, int num)
 2 {
 3     if (array == NULL || len == 0)
 4     {
 5         return false;
 6     }
 7     int L = 0;
 8     int R = len + 1;
 9     int mid = 0;
10     while (L < R)
11     {
12         mid = L + ((R - L) >> 1);
13         if (array[mid] == num)
14         {
15             return true;
16         }
17         else if (array[mid] < num)
18         {
19             R = mid - 1;
20         }
21         else if (array[mid] > num)
22         {
23             L = mid + 1;
24         }
25     }
26     return array[L] == num;
27 }

用二分法解決問題

題目：在一個有序陣列中，找>=某個數最左側的位置

 1 int binarySolve(int array[],int len,int num)
 2 {
 3     int L = 0;
 4     int R = len - 1;
 5     int mid = 0;
 6     int index = -1;
 7     while (L < R)
 8     {
 9         mid = L + ((R - L) >> 1);
10         if (array[mid] >= num)
11         {
12             index = mid;
13             R = mid - 1;
14         }
15         else
16         {
17             L = mid + 1;
18         }
19     }
20     return index;
21 }

用異或運算交換值

void Swap(int array[], int i, int j)
{
    array[i] = array[i] ^ array[j];
    array[j] = array[i] ^ array[j];
    array[i] = array[i] ^ array[j];
}

用異或運算解決問題

題目：一個陣列中有兩種數出現了奇數次，其他數都出現了偶數次，怎么找到這個兩個數

分析：

首先，將所有的數全部異或，然后得到的結果，就是奇數A與奇數B異或的結果，

因為異或相同的要變成0，所以說，A^B異或的結果肯定有一個1，

然后去取出這個結果最右側的1，提出來之后，再用這個1去跟所有的數去做與操作，

如果與操作的結果是1 ，那么就跟這個數進行異或操作，這樣就得出來了A或者B中的一個值

再用這個值去跟 A^B異或，然后得出另一個值，這兩個奇數答案就出來了，

 1 void findodd(int array[], int len)
 2 {
 3     int eor=0;
 4     for (int i = 0; i < len; i++)
 5     {
 6         eor ^= array[i];
 7     }
 8     //eor = a^b; 兩個奇數
 9     //現在要找出最右側的1
10     int rightone = eor & (~eor + 1);
11     //把有1的跟其中一組奇數進行異或
12     int onlyone = 0;
13     for (int i = 0; i < len; i++)
14     {
15         if ((rightone&array[i])!=0)
16         {
17             onlyone^= array[i];
18         }
19     }
20     int res = onlyone ^ eor;
21     cout << onlyone << "  " << res;
22 }

遞回解題

題目：求一個陣列中的最大值

 1 int process(int array[], int L, int R)
 2 {
 3     if (L == R)
 4     {
 5         return array[L];
 6     }
 7     int mid = L + ((R - L) >> 1);
 8     int left = process(array, L, mid);
 9     int right = process(array, mid + 1, R);
10     return max(left, right);
11 }
12 
13 int getMax(int array[], int len)
14 {
15     return process(array, 0, len - 1);
16 }

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/14525.html

標籤：其他

上一篇：二維陣列中的查找

下一篇：Cocos2d-x入門之旅[1]HelloWorld

演算法—第一周（7月25日——7月31日）

學習目錄：

選擇排序

冒泡排序

插入排序

歸并排序

二分法

異或運算