插入排序
/*
* Insertion_sort time complexity:
* Best-case: if the original sequence is sorted in a wanted-order: O(n)
* Worst-case: if the original array is sorted in a reverse order: O(n^2)
*/
void insertion_sort(int a[], int n)
{
int i, j, key;
for (j = 1; j < n; ++j) {
key = a[j];
i = j - 1;
while (i >= 0 && a[i] > key) {
a[i+1] = a[i];
--i;
}
a[i+1] = key;
}
}
冒泡排序
/*
* 算法复杂度 O(n^2)
*/
void BubbleSort(int a[], int n)
{
int i, j, temp;
//int flag = 0;
for (i = 0; i < n; ++i) {
//flag = 0;
for (j = n-1; j > i; --j) {
if (a[j] < a[j-1]) {
//flag = 1;
temp = a[j];
a[j] = a[j-1];
a[j-1] = temp;
}
}
// if (flag == 0)
// break;
}
}
选择排序：
/*
* Selection_sort(A)
* First find the smallest element of A and exchang it with A[1],
* then find the second smallest element of A and exchang it with A[2]
* continue this manner for the first n-1 elements of A.
* Runnig time:
* O(n^2) both in the Best and Worst-case.
*/
int find_min(int a[], int start, int end)
{
int i;
int res = start;
for (i = start+1; i < end; ++i)
if (a[res] > a[i])
res = i;
return res;
}
void selection_sort(int a[], int n)
{
int j, k;
int temp;
for (j = 0; j < n-1; ++j) {
k = j;
k = find_min(a, j, n);
if (k != j) { // if a[j] is already the smallest we don't do this
temp = a[k];
a[k] = a[j];
a[j] = temp;
}
}
}