智库建设网站方案,专门做讲座的英语网站,免费注册网站哪个好,深圳网站建设好快速排序#xff08;递归#xff09;
左指针指向第一个数据#xff0c;右指针指向最后一个数据。取第一个数据作为中间值。右指针指向的数据 循环与中间值比对#xff0c;若大于中间值#xff0c;右指针往左移动一位#xff0c;若小于中间值#xff0c;右指针停住。右…快速排序递归
左指针指向第一个数据右指针指向最后一个数据。取第一个数据作为中间值。右指针指向的数据 循环与中间值比对若大于中间值右指针往左移动一位若小于中间值右指针停住。右指针指向的数据放入左指针指向的位置。左指针指向的数据 循环与中间值比对若小于中间值左指针往右移动一位若大于中间值左指针停住。左指针指向的数据放入右指针指向的位置。重复2和3直到左指针和右指针指向同一个位置pos则中间值放入该位置pos。从中间值所在位置pos将数据分成左边和右边两部分。左边数值都比中间值小右边数值都比中间值大。重复1-5直到左边或右边只有一个数据。到此排序完成。
注左指针指向的数据始终比中间值小右指针指向的数据始终比中间值大。 时间复杂度最好情况 O(nlogn)最坏情况 O()平均情况 O(nlogn)
左右指针依次从头或从尾与中间值比对一轮比对约n次。若每次取的中间值正好是中间位置的数据每次都是对半拆分拆分层级logn则所有数据需约logn轮的比对总时间 约 O(nlogn)。若已经排好序了则每次取的中间值都是最小或最大值则每次都是依次从下一位数据重新开始类似斜树最坏时间约 O()。
空间复杂度最好情况 O(logn)最坏情况 O(n)。
在原位置排序使用栈作为辅助空间。每次递归中间值入栈递归结束中间值出栈。若最好情况拆分层级logn最多logn个中间值在栈中则即空间使用 O(logn)。若最坏情况则递归n次即空间使用约 O(n)。 C语言实现quicksort.c
#include stdio.h/* function prototype */
void quicksort(int *, int, int); // quick sort (recursion)
void traverse(int *, int); // show element one by one/* main function */
int main(void)
{int arr[] {4,2,6,9,5,1,3};int n sizeof(arr) / sizeof(int);traverse(arr, n);quicksort(arr, 0, n - 1);printf([ after quick sort ] );traverse(arr, n);return 0;
}
/* subfunction */
void quicksort(int *array, int start, int end) // quick sort (recursion)
{if(start end) return ;int low start, high end;int middata array[low]; // the first element as middle datawhile(low high){// right side, data is bigger than middle data.High index move a step to left while(low high array[high] middata) high--;// right side, if data is smaller than middle data, data change to low index array[low] array[high];// left side, data is smaller than middle data.Low index move a step to rightwhile(low high array[low] middata) low;// left side, if data is bigger than middle data, data change to high indexarray[high] array[low];}// the middle data in the correct positionarray[low] middata;// from the position of the middle data, split to two sidesquicksort(array, start, low - 1);quicksort(array, low 1, end);
}void traverse(int *array, int length) // show element one by one
{printf(elements(%d): , length);for(int k 0; k length; k){printf(%d , array[k]);}printf(\n);
} 编译链接 gcc -o quicksort quicksort.c 执行可执行文件 ./quicksort 归并排序递归
从中间位置将数据拆分成左右两部分。再分别将左右两部分从各自中间位置再拆分成左右两部分。直到左边或右边只有一个元素。将最多只有一个元素的左右两边排序合并在一起。将排好序的左右两边排序合并在一起。重复3直到全部排好序。 时间复杂度最好情况 O(nlogn)最坏情况 O(nlogn)平均情况 O(nlogn)
每次对半拆分拆分层级logn所有数据都需要比对 进行重新排序合并一轮比对合并约n次共约logn轮则总时间约 nlogn即 O(nlogn)。
空间复杂度O(n)
有多少数据就需要多少额外的空间存储 已排好序的数据即 O(n)。 C语言实现mergesort.c
#include stdio.h
#include math.h/* function prototype */
void mergesort(int *, int, int); // merge sort (recursion)
void traverse(int *, int); // show element one by one/* main function */
int main(void)
{int arr[] {4,2,6,9,5,1,3};int n sizeof(arr) / sizeof(int);traverse(arr, n);mergesort(arr, 0, n - 1);printf([ after merge sort ] );traverse(arr, n);return 0;
}
/* subfunction */
void mergesort(int *array, int start, int end) // merge sort (recursion)
{if(start end) return ;// from the middle, split the array to the left side and the right sideint mid start ceil((end - start) / 2);mergesort(array, start, mid);mergesort(array, mid 1, end);// merge the left and right, sort to the new arrayint tmparr[end - start 1];int i start, j mid 1;for(int k 0; k end - start; k){// the right side is over or left data right data, copy the left dataif(j end || (i mid array[i] array[j])){tmparr[k] array[i];i;}// the left side is over or left data right data, copy the right dataelse{tmparr[k] array[j];j;}}// elements in the new array copy to the original arrayfor(int i start, k 0; i end; i, k){array[i] tmparr[k];}
}void traverse(int *array, int length) // show element one by one
{printf(elements(%d): , length);for(int k 0; k length; k){printf(%d , array[k]);}printf(\n);
} 编译链接 gcc -o mergesort mergesort.c 执行可执行文件 ./mergesort 希尔排序
取一定间隔开始一般为数据量的一半将数据分为多个组每个组分别排序。将间隔减半数据分为多个组每个组分别排序。重复2直到间隔为1完成最后的排序。 时间复杂度O() - O()
插入排序的升级。先根据大间隔按组进行插入排序再依次减小间隔按组进行插入排序。比快但比nlogn慢。
空间复杂度O(1)
在原位置排序只重复使用了用于交换的临时空间不随数据量的变动而变动空间使用为常量(1)。 C语言实现shellsort.c
#include stdio.h
#include math.h/* function prototype */
void shellsort(int *, int); // shell sort
void traverse(int *, int); // show element one by one/* main function */
int main(void)
{int arr[] {4,2,6,9,5,1,3};int n sizeof(arr) / sizeof(int);traverse(arr, n);shellsort(arr, n);printf([ after shell sort ] );traverse(arr, n);return 0;
}
/* subfunction */
void shellsort(int *array, int length) // shell sort
{int gap ceil(length / 2); // steps of two comparative datawhile(gap 0){// from gap to the end, each element compare with data before gap stepsfor(int i gap; i length; i){// element cycle compare with data before gap steps, until 0 indexfor(int j i; j gap; j - gap){if(array[j] array[j - gap]){int tmp array[j];array[j] array[j - gap];array[j - gap] tmp;}}}// reduce the stepgap ceil(gap / 2);}
}void traverse(int *array, int length) // show element one by one
{printf(elements(%d): , length);for(int k 0; k length; k){printf(%d , array[k]);}printf(\n);
} 编译链接 gcc -o shellsort shellsort.c 执行可执行文件 ./shellsort
