简单的排序算法（数组，链表存储）

Posted on | In | Views:

冒泡排序：

数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
void bublletSort(int a[],int len)

{

  int temp;

  for(int i=0;i<len-1;i++)

  {

     for(int j=0;j<len-i;j++)

     {

        if(a[j]>a[j+1])

        {

           temp = a[j];

           a[j] = a[j+1];

           a[j+1] = temp;

        }

     }

  }

}

链表

1
2
3
4
5
6
7
8
9
10
11
12
13
void BubbletSort(LNode *head) 
{
       LNode *p,*q;
       int s;
    for(p=head->next;p!=NULL;p=p->next)
      for(q=p->next;q!=NULL;q=q->next)
        if((p->data)>(q->data))
         {
            s=p->data;
            p->data = q->data;
            q->data = s;
         }
}

插入

(原理)[https://blog.csdn.net/huangyimo/article/details/80888999]

数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
void insertSort(int a[],int n)

{

   for(int i=1;i<n;i++)

   {

      int key=a[i];//key 为哨兵 待插入的数据放入哨兵中

      int j=i-1;

      while(j>=0&&a[j]>key)//从哨兵开始从右往左开始遍历

      {

         a[j+1] = a[j];//数据往后移动一个位置

         j--;//从key开始遍历,j--表示往前移动一个位置,直至寻找到一个a[j]小于key

      }

      a[j+1] = key;

   }

}

链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
void InsertSort(LNode *L){

   LNode *p,*r,*q;

   p=L->next;     //表头的下一个，就是第一个，看作已经排好

   q=p->next;//q保存p的后继   //q是第二个

   p->next=NULL;   //已排好的部分的最后一个元素的next为null，这样就能知道一次比较是否到头。

   p=q;

   while(p!=NULL){

     q=p->next;  //每次保存等待比较元素的下一条

     r=L;

     while(r->next!=NULL&&r->next->data<p->data){

        r=r->next;   //比他小就下一个，从左往右

     }
//开始勾连，维护链表

     p->next = r->next;   //插进去

     r->next = p;

     p=q;  //利用保存的q，将p指向下一个要排序的

   }

}

选择排序

原理参考:

[[选择排序(数组实现)]]: https://blog.csdn.net/weixin_41362649/article/details/81901091

数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void selectSort(int a[],int len)
{
   int minindex,temp;//minindex-哨兵  temp-暂存空间
   for(int i=0;i<len;i++)
   {
      minindex=i;//设置哨兵为当前位置元素
      for(int j=i+1;j<len;j++)
      {
         if(a[j]<a[minindex]) minindex=j;//从左往右遍历哨兵(当前位置元素)往右的元素
                                         //找到比哨兵(当前位置元素)小的元素,把哨兵的位置让给它
                                         //找到的这个元素是数组中最小的元素
      }
      
      //a[i]与哨兵(最小的元素)交换位置
      temp = a[i];//a[i]为当前位置的元素,temp为暂存空间
      a[i] = a[minindex];
      a[minindex] = temp;
   }
}

链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

void SelectSort(LinkList &L)//简单选择排序

{

   LinkList p = L->next;

   LinkList minindex;//设置一个节点minindex

   LinkList q;

   int temp;

   while(p)//从第一个节点开始遍历

   {

     q=p->next;//第一个节点往右的节点

     minindex=p;//设置当前ｐ指针为最小，为这一趟选择排序开始的位置

     while(q)//

     {

       if(q->data<minindex->data) minindex=q;//在本趟中寻找最小的那个数

 

       q=q->next;

       

     }

        if(minindex!=p)//判断最小的数是否为当前的节点ｐ

      {

         temp = minindex->data;

         minindex->data = p->data;

         p->data = temp;

       }

     p=p->next;

   }

}

快速排序

(快速排序原理)[https://www.cnblogs.com/CBDoctor/articles/4077574.html]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
# include<iostream>
# include<cstdlib>
using namespace std;

void quickSort(int a[],int left,int right)
{
  int i,j,t,temp;
  if(left>=right) //作为后面递归结束的判断依据
     return;
  temp=a[left];//temp为基准数,该
  i=left;//i相当于左边的哨兵
  j=right;//j相当于右边的哨兵
  while(i!=j)
  {
     //从右往左开始寻找比temp小的数,直至找到为止
     while(a[j]>=temp&&i<j) j--;
    
     //从左往右开始寻找比temp大的数,直至找到为止
     while(a[i]<=temp&&i<j) i++;
     if(i<j)//交换位置
     {
       t=a[i];
       a[i]=a[j];
       a[j]=t;
     }
  }
  a[left]=a[i];//基准数归位
  a[i]=temp;
  quickSort(a,left,i-1);
  quickSort(a,i+1,right);
}

int main()
{
	int a[] = { 3,1,4,5,2,8,7,9,6,0 };

	int n=10;
	quickSort(a,0,9);

	for (int i = 0; i < 10; i++)
	{
		cout << a[i] << " ";

	}
	cout << endl;
	return 0;
}

摘自：

https://c0okb.github.io/2019/11/19/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E6%80%BB%E7%BB%93/