工作三年了，对算法也忘记好多了，今天抽空来总结一下排序算法吧
- 冒泡排序
思路：
用第一个元素与第二个元素对比，求出最大值或最小值
依次用对比第一个与第三个，寻求最大值或最小值递归
代码：
int sort(int * arr, int size) {
int tmp;
int i,j;
for(i = 0; i< size; i++) {
for(j = i+1; j < size; j++) {
if (arr[i] >= arr[j]) {
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
}
return 0;
}
- 插入排序
在洗牌的时候，选择新申明一个数组，取一个元素对比
int sort(int * arr, int size) {
int temp;
int i = 0, j = 0;
for(i = 1; i < size; i++) {
j = i - 1;
temp = arr[i];
while(j >= 0 && arr[j] > temp) {
arr[j + 1] = arr[j];
j--;
}
arr[j+1] = temp;
}
return 0;
}
- 快速排序
选取一个基准元素，通过从后向前遍历和从前向后遍历数组，把数组元素和基准元素进行比较，把数组分成两份，一份比基准元素大，一份比基准元素小，再利用分治策略从已经分好的两组中分别进行以上步骤，知道排序完成
void swap(int *x, int *y) {
int tmp = *x;
*x = *y;
*y = tmp;
}
int partition(int * arr, int left, int right)
{
int key = arr[left];
while(left < right) {
while(left < right && arr[right] >= key)
--right;
swap(arr + left, arr + right);
while(left< right && arr[left] <= key)
++left;
swap(arr +left , arr + right);
}
return left;
}
int sort(int arr[], int left, int right)
{
if (left >= right)
return 0;
int mid = partition(arr, left, right);
sort(arr, left, mid - 1);
sort(arr, mid+1, right );
return 0;
}
