正文

算法5--排序

taoliu_alex  taoliu_alex  2022-08-05  170

关键词：

主要是一些常见的排序方法的实现

1 冒泡排序算法

排序算法的理论和实现比较简单；

对于冒泡排序算法的改进，一种比较好的方法是，每次中间排序之后，都进行排序状态检测，如果已经排好序，就退出排序过程，否则基于冒泡排序；

但是：对于数组排序状态的检测，我没有比较好的办法；如果个数比较少，还可以容易得出，但是数组元素个数比较多的时候，该如何做？

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <time.h>
 4 
 5 #define SIZE 10
 6 
 7 int sortjudge(int *a,int len)
 8 {
 9     if (/* condition */)
10     {
11         /* code */
12     }
13 }
14 void bubblesort(int *a,int len)
15 {
16     int temp;
17     for (int i = 0; i < len-1; i++)
18     {
19         for (int j = len-1; j>i; j--)
20         {
21             if (a[j-1]>a[j])
22             {
23                 temp=a[j-1];
24                 a[j-1]=a[j];
25                 a[j]=temp;
26             }
27         }
28         printf("the %d down sort answer :", i+1);
29         for (int k = 0; k < len; k++)
30         {
31             printf("%d ", a[k]);
32         }
33         printf("
");
34     }
35 
36 }
37 
38 
39 int main()
40 {
41     int array[SIZE];
42     srand(time(NULL));
43     for (int i = 0; i < SIZE; i++)
44     {
45         array[i]=rand()/1000;
46     }
47     printf("before sort:
");
48     for (int j = 0; j < SIZE; j++)
49     {
50         printf("%d ",array[j]);
51     }
52     printf("
");
53     bubblesort(array,SIZE);
54     printf("after sort:
");
55     for (int k = 0; k < SIZE; k++)
56     {
57         printf("%d ",array[k]);
58     }
59     printf("
");
60     return 0;
61 }

2 选择排序

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <time.h>
 4 
 5 #define SIZE 10
 6 
 7 void selectionsort(int *a , int len)
 8 {
 9     int temp;
10     for (int i=0; i<len-1; i++)
11     {
12         int k=i;
13         for (int j=i+1; j<len; j++)
14         {
15             if (a[j]<a[k])
16             {
17                 k=j;
18             }
19         }
20         if (k!=i)
21         {
22             temp=a[i];
23             a[i]=a[k];
24             a[k]=temp;
25         }
26         printf("the %d sorted answer is :" , i+1);
27         for (int m = 0; m<len; m++)
28         {
29             printf("%d",a[m]);
30         }
31         printf("
");
32     }
33 }
34 
35 
36 int main()
37 {
38     int array[SIZE];
39     srand(time(NULL));
40     for (int i = 0; i < SIZE; i++)
41     {
42         array[i]=rand()/1000;
43     }
44     printf("before sort:
");
45     for (int j = 0; j < SIZE; j++)
46     {
47         printf("%d ",array[j]);
48     }
49     printf("
");
50     selectionsort(array,SIZE);
51     printf("after sort:
");
52     for (int k = 0; k < SIZE; k++)
53     {
54         printf("%d ",array[k]);
55     }
56     printf("
");
57     return 0;
58 }

3 插入排序

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <time.h>
 4 
 5 #define SIZE 10
 6 
 7 void insertionsort(int *a,int len)
 8 {
 9     for (int i = 1; i < len; i++)
10     {
11         int t=a[i];
12         int j=i-1;
13         while(j>=0&&t<a[j])
14         {
15             a[j+1]=a[j];
16             j--;
17         }
18         a[j+1]=t;
19         printf("the %d step sort answer:", i);
20         for (int k = 0; k < len; k++)
21         {
22             printf("%d ",a[k] );
23         }
24         printf("
");
25     }
26 }
27 
28 int main()
29 {
30     int array[SIZE];
31 
32     srand(time(NULL));
33 
34     for (int i = 0; i < SIZE; i++)
35     {
36         array[i]=rand()/1000+100;
37     }
38     printf("before sort:
");
39     for (int j = 0; j < SIZE; j++)
40     {
41         printf("%d ",array[j]);
42     }
43     printf("
");
44     insertionsort(array,SIZE);
45     printf("after sort:
");
46     for (int k = 0; k < SIZE; k++)
47     {
48         printf("%d ",array[k]);
49     }
50     printf("
");
51     return 0;
52 }

4 shell排序

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define SIZE 10

void shellsort(int *a,int len)
{
    int times=0;
    for (int i = len/2; i >=1; i/=2)
    {
        for (int j = i; j < len; j++)
        {
            int temp=a[j];
            int k=j-i;
            while(k>=0&&temp<a[k])
            {
                a[k+i]=a[k];
                k-=i;
            }
            a[k+i]=temp;
        }
        times=times+1;
        printf("the %d steps answer:", times);
        for (int h = 0; h < len; h++)
        {
            printf("%d ",a[h]);
        }
        printf("
");
    }
}
int main()
{
    int array[SIZE];
    srand(time(NULL));
    for (int i = 0; i < SIZE; i++)
    {
        array[i]=rand()/1000+100;
    }
    printf("before sort:
");
    for (int j = 0; j < SIZE; j++)
    {
        printf("%d ",array[j]);
    }
    printf("
");
    shellsort(array,SIZE);
    printf("after sort:
");
    for (int k = 0; k < SIZE; k++)
    {
        printf("%d ",array[k]);
    }
    printf("
");
    return 0;
}

5 快速排序

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <time.h>
 4 
 5 #define SIZE 10
 6 
 7 void exchange(int m,int n)
 8 {
 9     int temp=0;
10     temp=m;
11     m=n;
12     n=temp;
13 }
14 
15 int partion(int *a,int left,int right)
16 {
17     int x=a[right];
18     int i=left;
19     for (int j=left ; j <= right; j++)
20     {
21         if (a[j]<=x)
22         {
23             i=i+1;
24             exchange(a[i],a[j]);
25         }
26     }
27     exchange(a[i+1],a[right]);
28     printf("the partion postion is 
", i);
29     return i;
30 }
31 
32 
33 void quicksort(int *a,int left,int right)
34 {
35     if (left<right)
36     {
37         int q=partion(a,left,right);
38         quicksort(a,left,q-1);
39         quicksort(a,q+1,right);
40     }
41 }
42 
43 int main()
44 {
45     int array[SIZE];
46 
47     srand(time(NULL));
48 
49     for (int i = 0; i < SIZE; i++)
50     {
51         array[i]=rand()/1000+100;
52     }
53     printf("before sort:
");
54     for (int j = 0; j < SIZE; j++)
55     {
56         printf("%d ",array[j]);
57     }
58     printf("
");
59 
60     quicksort(array,0,SIZE-1);
61 
62     printf("after sort:
");
63     for (int k = 0; k < SIZE; k++)
64     {
65         printf("%d ",array[k]);
66     }
67     printf("
");
68     return 0;
69 }

6 堆排序

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <time.h>
 4 
 5 #define SIZE 10
 6 
 7 int left(int i){return i*2;}
 8 
 9 int right(int i){return i*2+1;}
10 
11 int parent(int i){return i/2;}
12 
13 void swap(int a,int b)
14 {
15     int tem=a;
16     a=b;
17     b=tem;
18 }
19 
20 void max_heapify(int *a,int i)
21 {
22     int length=SIZE;
23     int l=left(i);
24     int r=right(i);
25     int largest;
26     if (l<=SIZE&&a[l]>a[i])
27     {
28         largest=l;
29     }
30     else
31         largest=i;
32     if (r<=length&&a[r]>a[i])
33     {
34         largest=r;
35     }
36     if (largest!=i)
37     {
38         swap(a[largest],a[i]);
39         max_heapify(a,largest);
40     }
41 }
42 
43 void build_max_heap(int *a)
44 {
45     int length=SIZE;
46     for (int i = length/2; i >0; i--)
47     {
48         max_heapify(a,i);
49     }
50 }
51 
52 
53 void heapsort(int *a)
54 {
55     int length=SIZE;
56     build_max_heap(a);
57 
58     for (int i = length; i >=2; i--)
59     {
60         printf("%d ", a[0]);
61         swap(a[0],a[i]);
62         length=length-1;
63         max_heapify(a,1);
64     }
65 }
66 
67 
68 int main()
69 {
70     int array[SIZE];
71     int length=10;
72     srand(time(NULL));
73 
74     for (int i = 0; i < SIZE; i++)
75     {
76         array[i]=rand()/1000+100;
77     }
78     printf("before sort:
");
79     for (int j = 0; j < SIZE; j++)
80     {
81         printf("%d ",array[j]);
82     }
83     printf("
");
84 
85     heapsort(array);
86 
87     printf("after sort:
");
88     for (int k = 0; k < SIZE; k++)
89     {
90         printf("%d ",array[k]);
91     }
92     printf("
");
93     return 0;
94 }

7 归并排序

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include <time.h>
  4 
  5 #define SIZE 10
  6 #define big NULL
  7 /*
  8 void merge(int *a,int p,int q,int r)
  9 {
 10     int len1=q-p+1;
 11     int len2=r-q+1;
 12     int len3=len1+1;
 13     int len4=len2+1;
 14     int l[len3]={};
 15     int r[len4]={};
 16     for (int i = 0; i < len1; i++)
 17     {
 18         l[i]=a[p+i-1];
 19     }
 20     for (int j = 0; j < len2; j++)
 21     {
 22         r[j]=a[q+j];
 23     }
 24     int l[len3]=big;
 25     int r[len4]=big;
 26     int i=1;
 27     int j=1;
 28     for (int k = p; k < r; k++)
 29     {
 30         if (l[i]<=r[j]&&l[i]!=big&&r[j]!=big)
 31         {
 32             a[k]=l[i];
 33             i++;
 34         }
 35         else
 36         {
 37             a[k]=r[j];
 38             j++;
 39         }
 40     }
 41 }
 42 */
 43 void merge2(int *a,int p,int q,int r)
 44 {
 45     int len1=q-p+1;
 46     int len2=r-q+1;
 47     int len3=r-p+1;
 48     int left[len1];
 49     int right[len2];
 50     for (int i = 0; i < len1; i++)
 51     {
 52         left[i]=a[p+i-1];
 53     }
 54     for (int j = 0; j < len2; j++)
 55     {
 56         right[j]=a[q+j];
 57     }
 58     while(len1>=0&&len2>=0)
 59     {
 60         a[len3--]=left[len1]>=right[len2] ? left[len1] : right[len2];
 61     }
 62     while(len1>0)
 63     {
 64         a[len3--]=left[len1--];
 65     }
 66     while(len2>0)
 67     {
 68         a[len3--]=right[len2--];
 69     }
 70 
 71 }
 72 
 73 
 74 void mergesort(int *a,int p,int r)
 75 {
 76     if (p<r)
 77     {
 78         int q=(p+r)/2;
 79         mergesort(a,p,q);
 80         mergesort(a,q+1,r);
 81         merge2(a,p,q,r);
 82     }
 83 }
 84 
 85 int main()
 86 {
 87     int array[SIZE];
 88 
 89     srand(time(NULL));
 90 
 91     for (int i = 0; i < SIZE; i++)
 92     {
 93         array[i]=rand()/1000+100;
 94     }
 95     printf("before sort:
");
 96     for (int j = 0; j < SIZE; j++)
 97     {
 98         printf("%d ",array[j]);
 99     }
100     printf("
");
101 
102     mergesort(array,0,SIZE-1);
103 
104     printf("after sort:
");
105     for (int k = 0; k < SIZE; k++)
106     {
107         printf("%d ",array[k]);
108     }
109     printf("
");
110     return 0;
111 }

算法5--排序

主要是一些常见的排序方法的实现1冒泡排序算法排序算法的理论和实现比较简单；对于冒泡排序算法的改进，一种比较好的方法是，每次中间排序之后，都进行排序状态检测，如果已经排好序，就退出排序过程，否则... 查看详情

排序算法——归并排序

归并排序遵循分治原则先将数组不断的递归二分打散，打散后再进行二二组合。原理如下数组：分[1,2,3,4,5,6,7,8]分[1,2,3,4],[5,6,7,8]分[1,2],[3,4],[5,6],[7,8]分[1],[2],[3],[4],[5],[6],[7],[8]治：[2,1],[4,3],6,5],[8,7]治：[4,3,2,1],[8,7,6,5]治：[8,7,6,5,4,3,... 查看详情

排序算法——选择排序

选择排序是排序方法中最简单效率最低的算法该方法会遍历（N2）/2：每次抽一位最小数或者最大数放在数组头部。再遍历抽取剩下的数组最小数如下所示：原数组：9，8，7，6，5，4，3，2，1第一轮：1，8，7，6，5，4，3，2，9第... 查看详情

java实现的5大排序算法

Java实现的5大排序算法排序算法很多地方都会用到，近期又重新看了一遍算法，并自己简单地实现了一遍，特此记录下来，为以后复习留点材料。　　废话不多说，下面逐一看看经典的排序算法：　　1、Java排序算法之选择排序... 查看详情

5.排序算法2

图解1.选择排序/**选择排序**在未排序序列中找到最小元素，存放到排序序列的起始位置再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。*以此类推，直到所有元素均排序完毕。*/int[]num={2,3,1,5,4};//控制遍历次数... 查看详情

排序算法总结

再一次复习排序算法,总结记录一下一先看两个不同的递归deffunc3(x):ifx>0:print(x)func3(x-1)deffunc4(x):ifx>0:func4(x-1)print(x)func3(5)func4(5)func3(5)输出5,4,3,2,1func4(5)输出1,2,3,4,5要理解这两个递归的不同,func3是递归进去的时候进行打印,... 查看详情

排序算法5--交换排序--快速排序

...的速度。快速排序方法中一次交换可以消除多个逆序算法方法：　　从右侧找第一个比key值小的进行交换，从左侧找第一个比key值大的进行交换，但是交换的并非是key值　　最查看详情

冒泡排序算法(代码片段)

importcn.idestiny.util.GeneratedArray;/***@Auther:FAN*@Date:2018/8/2521:21*@Description:冒泡排序*1)4,2,5,3,7,1*2)2,4,3,5,1,7*3)2,3,4,1,5,7*4)2,3,1,4,5,7*5)2,1,3,4,5,7*6)1,2,3,4,5,7**/publicclassBubbleSort 查看详情

算法5--排序--mergesortedarray

...好了，以后会慢慢开放的今天再更新一个有关排序的算法题1 MergeSortedArray描述GiventwosortedintegerarraysAandB,mergeBintoAasonesortedarray.Note:YoumayassumethatAhasenoughspa 查看详情

多种排序算法整理

最近面试一直问到排序，老是各种搞混，特地来整理整理先盗用一张图：说明：内部排序基于内存，外部排序是数据量大，而内存与外存的相结合的排序一、插入排序　　关键词：插入，将数字插入到一条已经排好序的有序表中... 查看详情

排序算法

选择排序：O(n^2)不稳定a={5,2,8,4,9,1}第一趟i=0：最小1,1和5交换：1, 2,8,4,9,5第二趟i=1：最小2, 1,2, 8,4,9,5第三趟i=2：最小4,4和8交换：1,2,4, 8,9,5第四趟i=3：最小5,5和8交查看详情

排序算法——归并排序(代码片段)

算法思想归并排序的主要思想就是将一个待排序列，①不断地一分为二划分成一个元素组成序列，一个元素组成的序列也就是有序序列，②然后再合并将相邻的两个有序序列，最终待排序列变成一个有序序列。总之，归并算法就... 查看详情

java实现的5大排序算法

Java实现的5大排序算法　　1、Java排序算法之选择排序　　选择排序的基本思想是遍历数组的过程中，以i代表当前需要排序的序号，则需要在剩余的[i…n-1]中找出其中的最小值，然后将找到的最小值与i指向的值进行交换。因为每... 查看详情

常见的排序算法(代码片段)

常见排序算法有1.选择排序2.插入排序3.冒泡排序4.快速排序5.归并排序这里写了5种排序的javademo，还有很多排序，希尔排序，计数排序，堆排序，基数排序等Sort.javapublicclassSortpublicstaticvoidmain(String[]args)int[]arr=3,6,9,2,5,4;int[]temp=newint... 查看详情

插入排序算法的学习

插入排序算法：例如序列：5，6，3，7，8，2采用插入排序算法对序列进行排序，具体步骤如下：第一步：将6单独提取出来，放在一个变量中去寄存；然后让5与寄存项进行比较，不满足前项大于寄存项，保持原有序列不变序列为... 查看详情

选择排序算法(代码片段)

importcn.idestiny.util.GeneratedArray;/***@Auther:FAN*@Date:2018/8/2520:11*@Description:选择排序每次排序选择出最小的数字放在对应位置*1）3，5，1，2最小值1和3交换*2）1，5，3，2最小值2和5交换*3）1，2，3，5排序完成**/publicclassSelectionSortpublicstatic 查看详情

java实现的常用5大排序算法

排序算法很多地方都会用到，近期又重新看了一遍算法，并自己简单地实现了一遍，特此记录下来，为以后复习留点材料。　　废话不多说，下面逐一看看经典的排序算法：　　1、Java排序算法之选择排序　　选择排序的基本思... 查看详情

排序算法之nb三人组

快速排序思路:例如：一个列表[5,7,4,6,3,1,2,9,8],1.首先取第一个元素5,以某种方式使元素5归位,此时列表被分为两个部分,左边的部分都比5小,右边的部分都比5大,这时列表变成了[2,1,4,3,5,6,7,9,8]2.再对5左边进行递归排序,取5左边部分的... 查看详情