Last active
September 16, 2017 02:05
-
-
Save linnet8989/14af49ae067544634d155c42b0edb8e0 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
void swap(int arr[], int i, int j) | |
{ | |
int temp = arr[i]; | |
arr[i] = arr[j]; | |
arr[j] = temp; | |
} | |
//bubble | |
void f1(int arr[], int length) | |
{ | |
for (int i = 0; i < length - 1; i++) | |
{ | |
for (int j = 0; j < length - i - 1; j++) | |
{ | |
if (arr[j] > arr[j + 1]) | |
{ | |
swap(arr, j, j + 1); | |
} | |
} | |
} | |
} | |
//selection | |
void f2(int arr[], int length) | |
{ | |
for (int i = 0; i < length - 1; i++) | |
{ | |
int indexOfMin = i; | |
for (int j = i; j < length; j++) | |
{ | |
if (arr[indexOfMin] > arr[j]) | |
{ | |
indexOfMin = j; | |
} | |
} | |
swap(arr, i, indexOfMin); | |
} | |
} | |
//insertion | |
void f3(int arr[], int length) | |
{ | |
for (int i = 0; i < length - 1; i++) | |
{ | |
int last = arr[i + 1]; | |
int j; | |
for (j = i + 1; j >= 1 && arr[j - 1] > last; j--) | |
{ | |
arr[j] = arr[j - 1]; | |
} | |
arr[j] = last; | |
} | |
} | |
//shell | |
void f4(int arr[], int length) | |
{ | |
int gap = length / 2; | |
while (gap != 0) | |
{ | |
for (int h = 0; h < gap; h++) | |
{ | |
//gap为1时,等效于平常的插入排序 | |
for (int i = h + gap; i < length; i += gap) | |
{ | |
int last = arr[i]; | |
int j; | |
for (j = i; j >= gap && arr[j - gap] > last; j -= gap) | |
{ | |
arr[j] = arr[j - gap]; | |
} | |
arr[j] = last; | |
} | |
} | |
gap = gap / 2; | |
} | |
} | |
void QuickSort(int arr[], int first, int last) | |
{ | |
int index; | |
if (first < last) | |
{ | |
index = Partition(arr, first, last); | |
QuickSort(arr, first, index - 1); | |
QuickSort(arr, index + 1, last); | |
} | |
} | |
int Partition(int arr[], int first, int last) | |
{ | |
int i, j, x; | |
i = first + 1; | |
j = last; | |
x = arr[first]; | |
while (true) | |
{ | |
while (arr[i] < x) i++; | |
while (arr[j] > x) j--; | |
if (i >= j) | |
break; | |
swap(arr, i, j); | |
} | |
arr[first] = arr[j]; | |
arr[j] = x; | |
return j; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment