- 冒泡排序
- 插入排序
- 希尔排序
- 选择排序
- 快速排序
- 归并排序
- 桶排序
- idea
每次交换相邻的两个元素，一趟排序过程下来后，最大的一个数排到了最后一位。第二趟下来之后，第二大的数就排到了倒数第二位。
因此，冒泡排序需要进行n-1趟。
如图：
- Code
void bubble_sort(int a[],int n){
for(int i=0;ia[j+1]){
int tmp = a[j];
a[j]=a[j+1];
a[j+1] = tmp;
}
}
}
}
- Complexity
- time complexity :
the best : O(n)
the worst : O(n^2) - space complexity: O(1)
- Idea
在待排序的元素中，假设前n-1个元素已有序，现将第n个元素插入到前面已经排好的序列中，使得前n个元素有序。按照此法对所有元素进行插入，直到整个序列有序。
但我们并不能确定待排元素中究竟哪一部分是有序的，所以我们一开始只能认为第一个元素是有序的，依次将其后面的元素插入到这个有序序列中来，直到整个序列有序为止。
- Code
void insert_sort(int a[],int n){
for(int i=1;i=0 && a[j]>key){
a[j+1] = a[j];
j--;
}
a[j+1]=key;
}
}
- Complexity
- time complexity :
the best : O(n)
the worst : O(n^2) - space complexity: O(1)
- Idea
其基本思想是：
1.先选定一个小于N的整数gap作为第一增量，然后将所有距离为gap的元素分在同一组，并对每一组的元素进行直接插入排序。然后再取一个比第一增量小的整数作为第二增量，重复上述操作…
2.当增量的大小减到1时，就相当于整个序列被分到一组，进行一次直接插入排序，排序完成。 - Code
void shell_sort(int a[],int n){
for(int d = n/2;d>=1;d/=2){
for(int i=d;i=0 && a[j]>key){
a[j+d] = a[j];
j-=d;
}
a[j+d]=key;
}
}
}
- Complexity
- time complexity : O(nlogn)
- average time complexity : O(n^1.3)
- space complexity: O(1)
- Idea
先在未排序数列中找到最小或最大的元素，交换到已排序数列的末尾，然后再从剩余未排序数列中继续寻找最小的元素或最大的元素继续做交换，以此类推，直到所有元素都排序完。 - Code
void select_sort(int a[],int n){
for(int i=0;i
- Complexity
- time complexity : O(n^2)
- space complexity: O(1)
快速排序
- Idea
挖坑法：
1.选出一个数据（一般是最左边或是最右边的）存放在key变量中，在该数据位置形成一个坑
2、还是定义一个L和一个R，L从左向右走，R从右向左走。（若在最左边挖坑，则需要R先走；若在最右边挖坑，则需要L先走）
3、在走的过程中，若R遇到小于key的数，则将该数抛入坑位，并在此处形成一个坑位，这时L再向后走，若遇到大于key的数，则将其抛入坑位，又形成一个坑位，如此循环下去，直到最终L和R相遇，这时将key抛入坑位即可。（选取最左边的作为坑位）
经过一次单趟排序，最终也使得key左边的数据全部都小于key，key右边的数据全部都大于key。
然后也是将key的左序列和右序列再次进行这种单趟排序，如此反复操作下去，直到左右序列只有一个数据，或是左右序列不存在时，便停止操作。
- Code
void quick_sort(int a[],int L,int R){
if(L>=R) return ;
int left = L,right = R;
int key = a[L];
while(left=key){
right--;
}
if(left=right) a[left]=key;
quick_sort(a,L,right-1);
quick_sort(a,left+1,R);
}
- Complexity
- time complexity : O(nlogn)
- space complexity: O(1)
归并排序
- Idea
分治法：
对序列的元素进行逐层折半分组，然后从最小分组开始比较排序，合并成一个大的分组，逐层进行，最终所有的元素都是有序的
- Code
#define SIZE 201
int b[SIZE];
void merge_sort(int a[],int L,int R){
if(L >= R) return;
int mid = L +(R-L)/2;
merge_sort(a,L,mid);
merge_sort(a,mid+1,R);
int i = L ,j = mid +1;
int k = L;
while(i<=mid && j<=R ){
if(a[i]
- Complexity
- time complexity : O(nlogn)
- space complexity: O(n)
桶排序
-
Idea
创建一个桶，桶的大小是原排序数组中的绝对值中的最大值。
-
Code
int b[20002];
void bucket_sort(int a[],int n){
for(int i=0;i
- Complexity
- time complexity : O(n)
- space complexity: O(M) M由原排序中的绝对值的最大值决定
