算法与数据结构:C语言的整数数组全排列(源码

作者:计算机教程

            闲来无事,研究了一个算法。这天气坐着都流汗。

最常见的七大排序算法,整理了下,包括时间复杂度和空间复杂度都做一个详细的解说,希望对需要的人能有所帮助。

 1 # include <stdio.h>
 2 # define N 3
 3 
 4 void swap(int arr[], int num1, int num2) {
 5         int t = arr[num1];
 6         arr[num1] = arr[num2];
 7         arr[num2] = t;
 8     }
 9     
10 void reverse(int arr[], int num1, int num2) {
11         int i;
12         for (i = 0; i < (num2 - num1) / 2; i ) {
13             swap(arr, num1   i, num2 - 1 - (i));
14         }
15     }
16 
17 int nextArr(int arr[]) {
18         int left = -1;
19         int right = -1;
20         int i;
21         for (i = N - 1; i > 0; i--) {
22             if (arr[i - 1] < arr[i]) {
23                 left = i - 1;
24                 break;
25             }
26         }
27         if (left < 0) {
28             return 0;
29         }
30 
31 
32         for (i = N - 1; i >= left; i--) {
33             if (arr[i] > arr[left]) {
34                 right = i;
35                 break;
36             }
37         }
38         swap(arr, left, right);
39         reverse(arr, left   1, N);
40         return 1;
41     }
42     
43 int sort(int arr[]){
44     int i,j,temp;
45     for(i=0;i<=N;i ){
46         for(j=0;j<N-i;j ){
47             if(arr[j]>arr[j 1]){
48                 temp=arr[j];
49                 arr[j]=arr[j 1];
50                 arr[j 1]=temp;
51             }
52         }
53     }
54     return arr[N];
55 }
56 
57 void syarrange(int arr[]){
58         int i;
59         arr[N]=sort(arr);
60         do{
61             for (i = 0; i < N; i ) {
62                 printf("%d ",arr[i]);
63             }
64             printf("n");
65         }while(nextArr(arr)==1);
66 }
67 
68 int main(){
69         int arr[N]={3,1,2};
70         syarrange(arr);
71         getchar();
72         return 0;
73 }

/**


* 1.插入排序算法

* @paramint[]  未排序数组

* @returnint[]  排完序数组

*

* 插入排序的基本思想是在遍历数组的过程中,假设在序号 i 之前的元素即 [0..i-1] 都已经排好序,

* 本趟需要找到 i 对应的元素 x 的正确位置 k ,并且在寻找这个位置 k 的过程中逐个将比较过的元素往后移一位,

* 为元素 x “腾位置”,最后将 k 对应的元素值赋为 x

*

* 一般情况下,插入排序的时间复杂度和空间复杂度分别为 O(n2 ) 和 O(1)

*/

public int[] sortInsert(int[] array){

for(int i=1;i

int temp = array[i];

int j;

for(j=i-1;j >= 0 && temp< array[j]; j--){

array[j 1] = array[j];

}

array[j 1] = temp;

}

return array;

}

/**

* 2.选择排序算法

* @paramint[]  未排序数组

* @returnint[]  排完序数组

*

* 选择排序的基本思想是遍历数组的过程中,以 i 代表当前需要排序的序号,则需要在剩余的 [i…n-1] 中找出其中的最小值,

* 然后将找到的最小值与 i 指向的值进行交换。因为每一趟确定元素的过程中都会有一个选择最大值的子流程,所以人们形象地称之为选择排序。

* 选择排序的时间复杂度和空间复杂度分别为 O(n2 ) 和 O(1)

*/

public int[] sortSelect(int[] arr){

for (int i = 0; i < arr.length; i ) {

int miniPost = i;

for (int m = i 1; m < arr.length; m ) {

if (arr[m] < arr[miniPost]) {

miniPost = m;

}

}

if (arr[i] > arr[miniPost]) {

int temp;

temp = arr[i];

arr[i] = arr[miniPost];

arr[miniPost] = temp;

}

}

return arr;

}

/**

* 3.冒泡排序算法

* @paramint[]  未排序数组

* @returnint[]  排完序数组

*

* 冒泡排序是將比較大的數字沉在最下面,较小的浮在上面

*

*/

public int[] sortBubble(int[] array){

int temp;

// 第一层循环:表明比较的次数, 比如 length 个元素,比较次数为 length-1 次(肯定不需和自己比)

for(int i=0;i

for (int j = array.length - 1; j > i; j--) {

if (array[j] < array[j - 1]) {

temp = array[j];

array[j] = array[j - 1];

array[j - 1] = temp;

}

}

}

return array;

}

/**

* 4.快速排序算法

* @paramint[]  未排序数组

* @returnint[]  排完序数组

* 通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,

* 则可以分别对这两部分记录继续进行排序,已达到整个序列有序的目的

* 本质就是,找一个基位(枢轴,分水岭,作用是左边的都比它小,右边的都比它大.可随机,取名base

* 首先从序列最右边开始找比base小的,如果小,换位置,从而base移到刚才右边(比较时比base小)的位置(记为临时的high位),这样base右边的都比base大

* 然后,从序列的最左边开始找比base大的

* ,如果大,换位置,从而base移动到刚才左边(比较时比base大)的位置(记为临时的low位),这样base左边的都比base小

* 循环以上两步,直到 low == heigh, 这使才真正的找到了枢轴,分水岭. 返回这个位置,分水岭左边和右边的序列,分别再来递归

*

*/

public int[] sortQuick(int[] array){

return quickSort(array, 0, array.length-1);

}

private  int[] quickSort(int[] arr, int low, int heigh) {

if (low < heigh) {

int division = partition(arr, low, heigh);

quickSort(arr, low, division - 1);

quickSort(arr, division 1, heigh);

}

return arr;

}

// 分水岭,基位,左边的都比这个位置小,右边的都大

private int partition(int[] arr, int low, int heigh) {

int base = arr[low]; //用子表的第一个记录做枢轴(分水岭)记录

while (low < heigh) {  //从表的两端交替向中间扫描

while (low < heigh && arr[heigh] >= base) {

heigh--;

}

// base 赋值给 当前 heigh 位,base 挪到(互换)到了这里,heigh位右边的都比base大

swap(arr, heigh, low);

while (low < heigh && arr[low] <= base) {

low ;

}

// 遇到左边比base值大的了,换位置

swap(arr, heigh, low);

}

// now low = heigh;

return low;

}

private  void swap(int[] arr, int a, int b) {

int temp;

temp = arr[a];

arr[a] = arr[b];

arr[b] = temp;

}

/**

* 5.合并排序算法

* @paramint[]  未排序数组

* @returnint[]  排完序数组

*

* 归并排序采用的是递归来实现,属于“分而治之”,将目标数组从中间一分为二,之后分别对这两个数组进行排序,

* 排序完毕之后再将排好序的两个数组“归并”到一起,归并排序最重要的也就是这个“归并”的过程,

* 归并的过程中需要额外的跟需要归并的两个数组长度一致的空间

*/

private int[] sort(int[] nums, int low, int high) {

int mid = (low high) / 2;

if (low < high) {

本文由nba买球发布,转载请注明来源

关键词: