生成隨機數(shù)
int * getrand(int min, int max, int len){
int* arr = (int*)malloc(sizeof(int)*len);
for(int i = 0; i < len; ++i) {
arr[i] = rand() % (max-min+1) + min;
}
return arr;
}
一、冒泡排序
算法原理：
比較兩個相鄰的元素胆屿，將值大的元素右移。
算法思路：
首先第一個元素和第二個元素比較偶宫，如果第一個大非迹，則二者交換，否則不交換纯趋；然后第二個元素和第三個元素比較憎兽，如果第二個大，則二者交換吵冒，否則不交換……一直執(zhí)行下去纯命，最終最大的那個元素被交換到最后，一趟冒泡排序完成痹栖。最壞的情況是排序是逆序的亿汞。
算法過程:
{1}{68,35,70,25,79,59,63,65}
{1,25}{68,35,70,79,59,63,65}
算法實現(xiàn):
void bubbleSort(int* arr,int len){
int t;
for (int i = 0; i < len - 1; i++)
{
for (int j = 0; j < len - 1 - i; ++j){
if (arr[j] > arr[j+1])
{
t = arr[j];
arr[j] = arr[j+1];
arr[j+1] = t;
}
}
}
}
插入排序
原理：基本思想是：通過一趟排序將要排序的數(shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小揪阿，然后再按此方法對這兩部分數(shù)據(jù)分別進行快速排序
栗子：我們有一個數(shù)組 arr[10] = {42,68,35,1,70,25,79,59,63,65};
思路：第一次循環(huán)
arr[0] 42與arr[1]比較 42 < 68 last不變
42 68 35 1 70 25 79 59 63 65
arr[0] 42與arr[2]比較 42 > 35 這時候讓arr[1]與arr[2]互換 last自增 數(shù)組：
42 35 68 1 70 25 79 59 63 65
以此類推
42 35 1 68 70 25 79 59 63 65
42 35 1 68 70 25 79 59 63 65
42 35 1 25 70 68 79 59 63 65
42 35 1 25 70 68 79 59 63 65
42 35 1 25 70 68 79 59 63 65
42 35 1 25 70 68 79 59 63 65
42 35 1 25 70 68 79 59 63 65
當結束循環(huán) arr[last] 與 原本的互換
25 35 1 42 70 68 79 59 63 65
void swap(int* arr, int l, int r) {
int tmp = arr[l];
arr[l] = arr[r];
arr[r] = tmp;
}
void QuickSort(int* arr ,int left, int right){
if(left >= right) // 若數(shù)組包含的元素少于兩個
return ;
int last = left; // 設左邊元素為子集劃分元素
for(int i= left + 1; i<= right; i++){ // 劃分子集
if(arr[i] < arr[left]){
swap(arr, ++last, i); // index 跟
}
printf("%d %d %d\n",i, arr[i],arr[left]);
//printArray(arr,10);
}
swap(arr, left, last); //回復劃分子集的元素
QuickSort(arr,left,last-1);
QuickSort(arr,last+1,right);
}
