简单排序算法
嵌入式方向要掌握的最简单的排序算法,先不说动态规划等其他算法,简单的也要会手撕。
本文不讲原理,只谈代码。
直接插入排序
void Insert_Sort(int* array, int size) {
for (int i = 1; i < size; i++) {
int temp = array[i];
int j = i - 1;
while (j >= 0 && array[j] > temp) {
array[j + 1] = array[j];
j--;
}
array[j + 1] = temp;
}
}
希尔排序
void shell_sort(int *array,int size){
int interval = size >> 1;
while(interval){
for(int i = interval; i < size; i++) {
int temp = array[i];
int j = i;
while(array[j - interval] > temp && j - interval >= 0) {
array[j] = array[j - interval];
j -= interval;
}
array[j] = temp;
}
interval >>= 1;
}
}
直接选择排序
void swap(int *array,int i,int j){
array[i] = array[i] + array[j];
array[j] = array[i] - array[j];
array[i] = array[i] - array[j];
}
void select_sort(int *array,int size){
for(int i = 0 ; i < size - 1 ; ++i){
int k = i ;
for(int j = i + 1 ; j < size ; ++j){
if(array[j]<array[k]) k=j;
}
swap(array,k,i);
}
}
冒泡排序
void bubble_sort(int *array,int size){
for(int i = 0 ; i < size - 1 ; ++i){
for(int j = 0; j < size - 1 - i ; ++j){
if(array[j] > array[j+1])swap(array,j,j+1);
}
}
}
快速排序
int paritition(int A[],int left,int right){
int mid = A[left];
while(left < right){
while(left < right && A[right] >= mid)right--;
A[left] = A[right];
while(left < right && A[left] <= mid)left++;
A[right] = A[left];
}
A[left] = mid;
return left;
}
void quickSort(int A[],int left,int right){
if(left < right){
int mid = paritition(A,left,right);
quickSort(A,left,mid-1);
quickSort(A,mid+1,right);
}
}
归并排序
void merge(int *list,int left,int mid,int right)
{
int i = left,j = mid+1;
int k = 0;
int temp[right-left];
while (i <= mid && j <= right)
{
if(list[i] < list[j])
temp[k++] = list[i++];
else
temp[k++] = list[j++];
}//当比较晚之后某数组还有剩余元素
while(i <= mid)temp[k++] = list[i++];
while(j <= right)temp[k++] = list[j++];
for(i = 0;i < k;i++)list[left+i] = temp[i];
}
int* merge_sort(int *list,int left,int right)
{
if(left < right)
{
int mid = (left + right) >> 1;
merge_sort(list,left,mid);
merge_sort(list,mid+1,right);
merge(list,left,mid,right);
}
return list;
}
吾心信其可行,
则移山填海之难,
终有成功之日!
——孙文
则移山填海之难,
终有成功之日!
——孙文
评论
0 评论