Zeray Rice

..

排序算法總結

嗯 這篇文章來總結下 排序算法 其實不算總結 是ceeji神牛幫我總結好的 我只是重新寫一遍 加點內容而已= =

順便在此再對ceeji牛表達深深的敬意

額 這一次的文章寫了好久= = 基本一星期之前就說要寫。。。一直沒寫。。（感覺好想在拖稿啊…）

順便說下 這次的目錄神馬的 是仿「可能吧」的 = =（我表示我是竊取複製的源代碼 不知道會不會有神馬法律問題=____,=）

一、插入排序

其實以前寫過一次插入排序 是在寫 算導筆記的時候…嗯 不過之後算導也擱置了 沒怎麼看來著…這回在這次總結中也給算進來把。

首先是一個算法過程圖 自己用excel畫的

Insert Sort

看這個圖就很清晰了 呃 忘記標號了 第一排的第一個階段 是初始未排序階段。

後面的每個階段有2個數組 一個數組是待排序的數組（上） 另外一個是排好序的數組（下）

第一步先從待排序的數組裏取出一個數 放入排好序的數組中 然後再向後選擇第二個數 和排好序的數組中 已經有的數進行 比較 然後 判斷應該放在這個數的前面還是後面 以此類推

下面是代碼部分

Insert Sort 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

void InsertSort()
{
  int i,j,m;
  for(i=0;i=result[i-1])
      {
          result[i]=num[i];
          continue;
      }
      for(j=0;jj;m--)
                  result[m]=result[m-1];
              result[i-1]=num[i];
              break;
          }
  }
}

這是我寫的 插入排序 寫的不好 num數組是待排序的 result數組是排好序的數組 先判斷是不是第一個數或者是不是比最後面的數大 如果是 就直接把這個要排序的數放到數列的最後 如果不是 則進入循環 掃描已排好序的序列 尋找要將這個待排序的數插入的地方 然後插入序列

嗯 插入排序就這樣差不多了 下面是 冒泡排序

二、冒泡排序

這個應該算是排序算法裏面最簡單的了 嗯 老師講的第一個排序算法。。。

先上圖

Bubble Sort

這個應該是比較好理解的 從 數組中第一個元素開始 兩兩依次比較大小 如果後面的數比前面的大（或者小） 則交換兩數位置 比較的次數爲 n-1 次 時間複雜度和插入排序相同 都是 O(n2)

Bubble Sort 
1
2
3
4
5
6
7
8
9
10
11
12
13

void BubbleSort()
{
  int i,j;
  int cache;
  for(i=0;inum[j+1])
          {
              cache=num[j];
              num[j]=num[j+1];
              num[j+1]=cache;
          }
      }
  }
}

冒泡排序的代碼相對來說簡單一些 寫著比較方便 如果對時間複雜度的要求不是太高 就可以用這個 來代替快排

三、選擇排序

選擇排序的原理是每次從待排序的數列中選出最大（或最小）的 然後放入排好序的數列的最前面或者最後面 先看圖:

Selection Sort

自認爲做的很清晰= = 很明白..用一個函數來返回數組中最大的數

Selection Sort - Get Max 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

int getmax()
{
  int max=0,large=0,i;
  for(i=0;i<n;i++)
  {
      if(num[i]==-1)
          continue;
      if(num[i]>=large)
      {
          large=num[i];
          max=i;
      }
  }
  return max;
}

然後用一個循環來把每次數列中的最大（或最小的數）排入序列

Selection Sort 
1
2
3
4
5
6
7
8
9
10

void SelectSort()
{
  int i,a;
  for(i=0;i<n;i++)
  {
      a=getmax();
      result[i]=num[a];
      num[a]=-1;
  }
}

這樣子就差不多了 每次將已經排過序的數賦值爲-1 這樣就不會再被選中了 嗯

好了 到這裏 簡單排序部分就完成了 下面是最後一部分 快速排序

四、快速排序

快速排序應該是 OI中最常用的排序算法了 所以很重要 代碼相對來說比較短（沒有堆排序長= =） 而且速度也快（沒有堆排序快..）嗯 可以無視掉括號裏的東西..

快排中 沿用了 冒泡排序的思想 加入了 分治思想 從而大大提高了效率 其實覺得維基百科上快排詞條的gif演示很清楚的說明了快速排序的過程：

Quick Sort

不過 快速排序的速度常常和 選擇的關鍵字有極大關係…所以 為了提高速度 引入了隨機化快排（換句話說。。拼RP = =）

整個排序過程是一個不斷遞歸的過程

下面是代碼（ceeji牛寫的 呃 我…我只是把這個背下來…）

Quick Sort 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

void quicksort(int* arrstart, int s, int t) //arrstart : 數組開始位置指針； s，t：排序的起始位置
{  if (s >= t) return;
  int i = s, j = t, x = arrstart[rand() % (t - s + 1) + s], tmp;
  while (i <= j)
  {
      while ((i < t)&&(arrstart[i] < x)) ++i;
      while ((j > s)&&(arrstart[j] > x)) --j;
      if (i <= j)
      {    tmp = arrstart[i];
          arrstart[i] = arrstart[j];
          arrstart[j] = tmp;
          ++i; --j;}
  }
  quicksort(arrstart, s, j);
  quicksort(arrstart, i, t);
}

不過 在編譯的時候 提醒 qsort已經在stdlib.h裏面定義了=_____________,=

然後發現原來stdlib.h裏本身就有快排了。。。。 上網搜了下… 使用方法是

qsort USAGE 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

/* qsort example */
#include <stdio.h>
#include <stdlib.h>

int values[] = { 40, 10, 100, 90, 20, 25 };

int compare (const void * a, const void * b)
{
  return ( *(int*)a - *(int*)b );
}

int main ()
{
  int n;
  qsort (values, 6, sizeof(int), compare);
  for (n=0; n<6; n++)
     printf ("%d ",values[n]);
  return 0;
}

呃 不过一直没有弄明白 compare这个函数是干嘛使的 = = 不过经过测试….上面ceeji牛写的快排以绝对优势胜出= = （数据..数据今天去找 ..找不到了。。。 然后也懒的去做了）

呃 好吧 这个排序总结终于到这儿结束了。。。嗯 爬走…（為神馬WP統計的 我寫的字數是300多 怨念。。）

Comments