2016年3月1日 星期二

strtok

#include "string.h"
#include "stdlib.h"
#include "stdio.h"
 
int main()
{
  char str[]="00:22:33:4B:55:5A";
  char *delim = ":";
  char * pch;
  printf ("Splitting string \"%s\" into tokens:\n",str);
  pch = strtok(str,delim);
  while (pch != NULL)
  {
    //int *a=malloc(strlen(pch)*sizeof(char))
//     int *a=strdup(pch)
    printf ("%s\n",pch);
    pch = strtok (NULL, delim);
  }     
  system("pause");
  return 0;
}
張貼者： 於 沒有留言:

2016年2月26日 星期五

LEET code -- Rotate Image

You are given an n x n 2D matrix representing an image.
Rotate the image by 90 degrees (clockwise).

Follow up:
Could you do this in-place?


下面這寫法要額外空間

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int size=matrix.size();
        vector<vector<int>> co(size,vector<int>(size,0));
        co=matrix;
        for(int i=0;i<size;i++){
            for(int j=0;j<size ;j++){
                matrix[j][size-i-1]=co[i][j];
            }
        }
    }
};

------------
每次轉四個角落
一起轉  不用額外空間

要注意邊界
左上 是 col會跑
左下  是row會跑
右上 是row會跑
右下 是col會跑


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int size=matrix.size();
        for(int row=0;row<size/2;row++){
            for(int col=row;col<size-1-row;col++){
                int temp=matrix[row][col];//left up
                matrix[row][col]=matrix[size-1-col][row];//left button
                matrix[size-1-col][row]=matrix[size-1-row][size-1-col];//right button
                matrix[size-1-row][size-1-col]=matrix[col][size-1-row];//right up
                matrix[col][size-1-row]=temp;
            }
        }

    }
};
張貼者： 於 沒有留言:
標籤：

LEET code -- Sort Colors

 Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note:
You are not suppose to use the library's sort function for this problem.


如果current 當下不等於 i (顏色)
就往後找  看有沒有  如果找不到就換 下一個顏色

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    void sortColors(vector<int>& nums) {
        int current=0;
        int size=nums.size();
        for(int i=0;i<3;i++){
            int color=current;
            while(color<size && current<size){
                if(nums[current]!=i){
                    color=current+1;
                    while(color<size && nums[color]!=i)color++;
                    if(color<size){
                        int temp=nums[color];
                        nums[color]=nums[current];
                        nums[current]=temp;
                    }else break;
                }
                current++;
                
            }
        }
    }
};




-----------


The solution requires the use of tracking 3 positions, the Low, Mid and High.
We assume that the mid is the "Unknown" area that we must evaluate.
If we encounter a 0, we know that it will be on the low end of the array, and if we encounter a 2, we know it will be on the high end of the array.
To achieve this in one pass without preprocessing (counting), we simply traverse the unknown will generating the low and high ends.
Take this example:
Assume our input is: 1 0 2 2 1 0 (short for simplicity).

Running the algorithm by hand would look something like:

    1 0 2 2 1 0
    ^         ^
    L         H
    M

    Mid != 0 || 2
    Mid++

    1 0 2 2 1 0
    ^ ^       ^
    L M       H

    Mid == 0
    Swap Low and Mid
    Mid++
    Low++

    0 1 2 2 1 0
      ^ ^     ^
      L M     H

    Mid == 2
    Swap High and Mid
    High--

    0 1 0 2 1 2
      ^ ^   ^
      L M   H

    Mid == 0
    Swap Low and Mid
    Mid++
    Low++

    0 0 1 2 1 2
        ^ ^ ^
        L M H

    Mid == 2
    Swap High and Mid
    High--

    0 0 1 1 2 2
        ^ ^
        L M
          H

    Mid <= High is our exit case



 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
class Solution {
    public:
    void sortColors(vector<int>& nums) 
    {
        int tmp = 0, low = 0, mid = 0, high = nums.size() - 1;

        while(mid <= high)
        {
            if(nums[mid] == 0)
            {
                tmp = nums[low];
                nums[low] = nums[mid];
                nums[mid] = tmp;
                low++;
                mid++;
            }
            else if(nums[mid] == 1)
            {
                mid++;
            }
            else if(nums[mid] == 2)
            {
                tmp = nums[high];
                nums[high] = nums[mid];
                nums[mid] = tmp;
                high--;
            }
        }
    }
};
張貼者： 於 沒有留言:
標籤：

LEET code -- Kth Smallest Element in a BST

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.
Note:
You may assume k is always valid, 1 ≤ k ≤ BST's total elements.
Follow up:
What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?
Hint:

  1. Try to utilize the property of a BST.
  2. What if you could modify the BST node's structure?
  3. The optimal runtime complexity is O(height of BST).

就是找出DFS他parse的順序找出來

為了可以提早結束  我用-1代表找到
rank代表現在找到第幾個數字了


 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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        if(root==NULL)return 0;
        rank=0;
        DFS(root,k);
        return reuslt;
        
    }
    int DFS(TreeNode* root,int level){
        if(root==NULL)return rank;
        int left=DFS(root->left,level);
        if(left<0)return -1;
        rank=rank+1;
        if(level==rank){
            reuslt=root->val;
            return -1;
        }
        int right=DFS(root->right,level);
        if(right <0)return -1;
        return 1;
    }
private:
    int rank;
    int reuslt;
};

--------------------------


 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
class Solution {
public:
    TreeNode* current = NULL;
    stack<TreeNode*> s;
    int kthSmallest(TreeNode* root, int k) {
        current = root;
        int count = 1;
        while(1)
        {
        while(current)
        {
            s.push(current);
            current = current->left;
        }
        if(count == k)
        {
            TreeNode* node = s.top();
            return node->val;
        }
        if(count != k)
        {
            TreeNode* node = s.top();
            s.pop();
            current = node->right;
            count++;
        }
        }
    }
};


張貼者： 於 沒有留言:
標籤：

LEET code -- Permutations

 Given a collection of distinct numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].


印出所有的排列組合，使樣回朔法來跑

用一個boo;陣列來記錄那些數字用過了
接著丟給下一個去紀錄


 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
class Solution {
public:
    void find(vector<vector<int>> &ans, vector<int> &current, vector<int> &nums, bool *use){
        if(current.size() == nums.size()){
            ans.push_back(current);
            return ;
        }
        for(int i=0;i<nums.size();i++){
            if(use[i]==false){
                current.push_back(nums[i]);
                use[i]=true;
                find(ans,current,nums,use);
                current.pop_back();
                use[i]=false;
            }
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        int size=nums.size();
        bool use[size]={0};
        vector<vector<int>> ans;
        vector<int> current;
        find(ans,current,nums,use);//not &use
        //for(int i=0;i<size;i++)use[i]=false;
        return ans;
    }
};

--------------------
旋轉的方式



 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
class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;
        create(nums,res,0);
        return res;
    }

    void create(vector<int>& nums,vector<vector<int>> &res,int n)
    {
        if(n==nums.size()-1)
            res.push_back(nums);
        else
        {
            for(int i=n;i<nums.size();i++)
            {
                swap(nums[i],nums[n]);
                create(nums,res,n+1);
                swap(nums[i],nums[n]);
            }
        }
    }

    void swap(int &a,int &b)
    {
        int tmp=a;
        a=b;
        b=tmp;
    }
};

張貼者： 於 沒有留言:
標籤：

LEET code -- Generate Parentheses

 Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:

"((()))", "(()())", "(())()", "()(())", "()()()"

下面利用Backtracking的方式  我現在選擇( 後面的選擇丟給下一個recursive來決定
leftsize代表有多少(   這個數目不能超過n
rightsize代表有多少)   這個數目不能超過( 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> ans;
        string s="(";
        findparent(ans,s,1,0,n);
        return ans;
    }
    
    void findparent(vector<string> &ans, string s,int leftsize,int rightsize,int n){//left is (   right is )
        if(n*2==leftsize+rightsize){
            ans.push_back(s);
            return;
        }
        if(leftsize<n)findparent(ans,s+"(",leftsize+1,rightsize,n);
        if(rightsize<leftsize)findparent(ans,s+")",leftsize,rightsize+1,n);
        
    }
};


-----------------------
-------------------------

 神人iterater

 logic here is simple:
First, store a result vector, then for every entry:
  • add '(', when cannot add ')'
  • add ')', when cannot add '('
  • copy this entry and add '(' and ')' separately to original and new copy, when both are valid
here count and countleft are vectors that store check values.

 

 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
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> result(1);
        vector<int> count(1,0),countleft(1,0);
        for(int i=0;i<2*n;++i){
            int m=count.size();
            for(int j=0;j<m;++j){
                if(count[j]==0){
                    result[j]+='(';
                    count[j]++;
                    countleft[j]++;
                }
                else if(countleft[j]==n) result[j]+=')';
                else{
                    result.push_back(result[j]+')');
                    count.push_back(count[j]-1);
                    countleft.push_back(countleft[j]);
                    result[j]+='(';
                    count[j]++;
                    countleft[j]++;
                }
            }
        }
        return result;
    }
};








張貼者： 於 沒有留言:
標籤：

LEET code -- Search a 2D Matrix

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
  • Integers in each row are sorted from left to right.
  • The first integer of each row is greater than the last integer of the previous row.

For example,
Consider the following matrix: 
[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

Given target = 3, return true.





可以發現  每一排的最後右邊一定最大
所以可以先搜尋 最右邊 去找要搜尋哪一排

但是我找到那排是用for loop找  會太慢  可以改成binary search


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        
        for(int i=0;i<matrix.size();i++){
            if(target <=matrix[i][ matrix[i].size()-1 ] ){
                for(int j=0;j<matrix[i].size();j++){
                    if(target == matrix[i][j])return true;
                }
                return false;
            }
        }
        return false;
    }
};

-------------
用binary search



 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        
        for(int i=0;i<matrix.size();i++){
            if(target <=matrix[i][ matrix[i].size()-1 ] ){
                int start=0,end=matrix[i].size()-1;
                while(start<=end){
                    int mid = start +(end-start)/2;//prevent overflow
                    if(matrix[i][mid]==target)return true;
                    if(matrix[i][mid] > target)end=mid-1;
                    else start=mid+1;
                }
                return false;
            }
        }
        return false;
    }
};





張貼者： 於 沒有留言:
標籤：

LEET code -- Binary Tree Level Order Traversal II

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).
For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its bottom-up level order traversal as:

[
  [15,7],
  [9,20],
  [3]
]


confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.


queue 的STL 注意是push 跟front 還有pop

reverse也是STL


 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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> ans;//initial ,empty
        queue<TreeNode*> parse;
        if(root==NULL)return ans;
        parse.push(root);
        while(parse.size()>0){
            vector<int> level;//local level
            for(int i=parse.size();i>0;i--){
                TreeNode * front = parse.front();
                level.push_back(front->val);
                if(front->left!=NULL)parse.push(front->left);
                if(front->right!=NULL)parse.push(front->right);
                parse.pop();
            }
            ans.push_back(level);
            
        }
        reverse(ans.begin(),ans.end());
        
    }
};

---------------------------
recursive



 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
class Solution {
public:

    vector< vector<int> > result;

    void dfs(TreeNode *root, int level)
    {
        if(!root) return;

        if(level == result.size()) 
            result.push_back( vector<int>() );

        vector<int> &vec = result[level];
        vec.push_back(root->val);

        dfs(root->left, level+1);
        dfs(root->right, level+1);
    }

    vector<vector<int>> levelOrderBottom(TreeNode* root)
    {
        if(!root) return vector< vector<int> >();

        dfs(root, 0);

        return vector< vector<int> >(result.rbegin(), result.rend());
    }
};

張貼者： 於 沒有留言:
標籤：

2016年2月25日 星期四

sort 整理

reference from
http://spaces.isu.edu.tw/upload/18833/3/web/sorting.htm

排序(sorting)
排序(Sorting)
第一類：內部與外部排序
第二類：穩定與不穩定排序法
第三類：簡單與高等排序法
常見之排序演算法
氣泡排序(Bubble sorting)
選擇排序(Selection sorting)
插入排序(Insertion sorting)
快速排序(Quick sorting)
堆積排序(Heap sorting)
薛爾排序(Shell sorting)
合併排序(Merge sorting)
基數排序(Radix sorting)

排序(Sorting)

返回主目錄
排序(sorting)，將一組資料一使用者需求，予以重新排列其順序。一般會依資料之大小順序排序(由大至小、或由小至大)。排序後之資料，優點為容易閱讀、統計分析、與快速搜尋所要之資料。
「資料結構」課程中，排序法分分類方式有三類：

第一類：內部與外部排序

內部排序(Internal sort)又稱「陣列排序」。
【定義】排序之工作，主要在主記憶體(RAM)完成。
【適用時機】資料量較少者。
外部排序(External sort)又稱「檔案排序」。
【定義】排序之工作，主要是在輔助記憶體(Disk, File)完成。
【適用時機】資料量較大者。
返回主目錄

第二類：穩定與不穩定排序法

穩定排序法(stable sorting)，如果鍵值相同之資料，在排序後相對位置與排序前相同時，稱穩定排序。
【例如】
排序前：3,5,19,1,3*,10
排序後：1,3,3*,5,10,19  (因為兩個3, 3*的相對位置在排序前與後皆相同。)
不穩定排序法(unstable sorting)，如果鍵值相同之資料，在排序後相對位置與排序前不相同時，稱不穩定排序。
【例如】
排序前：3,5,19,1,3*,10
排序後：1,3*,3,5,10,19  (因為兩個3, 3*的相對位置在排序前與後不相同。)
返回主目錄

第三類：簡單與高等排序法

簡單排序法
【定義】排序演算法簡單，但執行時間較長。
【平均時間複雜度】
高等排序法
【定義】排序演算法複雜，執行時間較短。
【平均時間複雜度】
返回主目錄

常見之排序演算法

常見之排序演算法：氣泡排序、選擇排序、插入排序、快速排序、堆積(heap)排序、薛爾(shell)排序、合併排序、基數排序
排序方法
最壞時間
平均時間
穩定
額外空間
備註說明
氣泡排序
Bubble
O(n2)
O(n2)
穩定
O(1)
n小比較好。
選擇排序
Selection
O(n2)
O(n2)
不穩定
O(1)
n小較好，部份排序好更好。
插入排序
Insertion
O(n2)
O(n2)
穩定
O(1)
大部份排序好比較好。
快速排序
Quick
O(n2)
O(nlog2n)
不穩定
O(n)~
O(log n)
在資料已排序好時會產生最差狀況。
堆積排序
Heap
O(nlog2n)
O(nlog2n)
不穩定
O(1)

薛爾排序
shell
O(ns)
1
O(n(log2n)2)
穩定
O(1)
n小比較好。
合併排序
Merge
O(nlog2n)
O(nlog2n)
穩定
O(n)
常用於外部排序。
基數排序
Radix
O(nlogbB)
O(n)~
O(nlogbk)
穩定
O(nb)
k:箱子數
b:基數
返回主目錄

氣泡排序(Bubble sorting)

資料結構中最簡單之排序法。所謂氣泡排序法就是相臨資料互相比較，若發現資料順序不對，就將資料互換。依次由上往下比，則結果將如氣泡般，依次由下往上浮起。
【分析】
1.      比較之回合數=資料數(n)-1。
2.        每一回合至少有一資料可以排列至正確之次序。
3.        時間複製度，最差與平均時間O(n2)
4.        需要一個額外(元素)空間。
5.        為一穩定排序。
6.        資料量小時，使用效果佳。
【原理】
1.        每一回合逐一比較相臨資料，依排序之順序交換位置。
2.        每回合至少會有一次交換位置，至沒交換位置則停止。
【演算法】
BubSort(int A[], int n)  //氣泡排序法之副程式
  {
    int i, j , k,t=1, Temp,sp;
    for (i=n-1; i>0; i--)
       {
        sp=1;
       for (j =0; j <=i; j++)
          if (A[j] > A[j+1])
             {  //兩數交換位置
               Temp = A[j];
               A[j] = A[j+1];
               A[j+1] = Temp;
               sp=0;
             }
             if (sp==1) break;          
       }
  }
返回主目錄

選擇排序(Selection sorting)

類似於氣泡排序法。主要差異在於，第n回合比較時，以一額外資料空間儲存目前第n大(小)，若發現資料順序不對，就將資料互換。依次由上往下比，則結果將由最大(最小)逐回合比較至最小(最大)。
【分析】
1.      比較之回合數=資料數(n)-1。
2.        時間複製度：最差與平均時間O(n2)
3.        需要一個額外(元素)空間。
4.        為一穩定排序。
5.        資料量小時，使用效果佳(優於氣泡)。
【原理】
1.        未排序前之第一筆資料可視為已排序好之資料
2.        每一回合逐一比較相臨資料，依排序之順序交換位置。
【演算法】
SelSort(int A[], int n)  //選擇排序法之副程式
 {
   int i, j, Temp, NP = 0;
   for (i = 1; i <= n - 1; i++)
    {
       NP = i;
       for (j = i + 1; j <= n; j++)
          if (A[j] > A[NP])  NP = j;
      {//相鄰兩個的資料交換位置
       Temp = A[i];
       A[i] = A[NP];
       A[NP] = Temp;
      }
    }
 }
返回主目錄

插入排序(Insertion sorting)

每次往後拿一筆記錄，依大小插入已排序好的記錄。也就是說，差入一個記錄在一堆已排好序之記錄中。任何未排序前之第一筆資料可視為已排序好之資料。
【分析】
1.        時間複製度，最差與平均時間O(n2)
2.        只需要一個額外(元素)空間。
3.        為一穩定排序。
4.        此方法適用於大部份資料已排序或已排序之資料庫新增資料後進行排序。
【原理】
1.        將待排序之資料逐一與已排序後之資料比較，再將資料放入適當位置。
2.        由最大(最小)逐回合比較至最小(最大)。
【演算法】
InSort(int A[], int n)  //插入排序法之副程式
 {
   int i, j, Temp;
   for (i = 1; i <= n; i++)
    {
     Temp=A[i];
     j=i-1;
     while (Temp
      {
        A[j+1]=A[j];
        j--;
        if(j==-1) break;
      }
      A[j+1]=Temp;
    }
 }
返回主目錄

快速排序(Quick sorting)

快速排序之觀念，找資料之中間值，將小於中間值放右邊，大於中間值放左邊，再以相同方法分左右兩邊序列，直到排序完成。
【分析】
1.        時間複製度，最差O(n2)與平均時間O(nlog2n)。
2.        需要額外堆疊空間。
3.        為不穩定排序。
4.        快速排序是平均時間最快之內部排序法。
【原理】
1.        取第一個記錄為鍵值K0，當中間值。
2.        由左而右找第一個Ki，使得Ki≧K0。由右而左找第一個Kj，使得Kj≦K0。也就是說，從左邊找比K0大，從右邊找比K0小。
3.        若i則Ki與Kj對調位置繼續步驟2；否則K0與Kj對調位置，並以j為基準，分為兩個未排序之序列。以遞迴呼叫方式對左右兩邊進行排序，直道完成排序。
4.        由最大(最小)逐回合比較至最小(最大)。
【演算法】
QuickSort(int A[], int left, int right)
{
    int i, j, s , Temp;
    if(left < right) {
        s = A[(left+right)/2];
        i = left - 1;
        j = right + 1;
        while(1) {
            while(A[++i] < s) ;  // 向右找
            while(A[--j] > s) ;  // 向左找
            if(i >= j) break;
               Temp = A[i];
               A[i] = A[j];
               A[j] = Temp;
        }
        QuickSort(A, left, i-1);   // 對左邊進行遞迴
        QuickSort(A, j+1, right);  // 對右邊進行遞迴
    }
}
返回主目錄

堆積排序(Heap sorting)

【分析】
1.        時間複製度，最差與平均時間O(nlog2n)。
2.        只需一額外記錄空間。
3.        為不穩定排序。
【原理】
1.        。
【演算法】
Heapsort(int A[]) {
    int i, m, p, s,t=1;
    m = MAX;
    while(m > 1) {
        SWAP(A[1], A[m]);
        m--;
        p = 1;
        s = 2 * p;
        while(s <= m) {
            if(s < m && A[s+1] < A[s])  s++;
            if(A[p] <= A[s])  break;
            SWAP(A[p], A[s]);
            p = s;
            s = 2 * p;
        }
    }
}

返回主目錄

薛爾排序(Shell sorting)

【分析】
1.        時間複製度，最差O(ns)與平均時間O(n(log2n)2)。
2.        為穩定排序。
【演算法】
Shellsort(int A[])
{
    int i, j, k, Gap, t;
    Gap = MAX / 2;
    while(Gap > 0)
     {
        for(k = 0; k < Gap; k++)
        {
            for(i = k+Gap; i < MAX; i+=Gap)
            {
                for(j = i - Gap; j >= k; j-=Gap)
                {
                    if(A[j] > A[j+Gap])
                    {
                        SWAP(A[j], A[j+Gap]);
                    }
                    else  break;
                }
            }
        }
        printf("\nGap = %d：", Gap);
        for(i = 0; i < MAX; i++)
            printf("%d ", A[i]);
        Gap /= 2;
    }
}

返回主目錄

合併排序(Merge sorting)

【演算法】
Mergesort(int A[], int M, int B[],int N, int C[])
 {
    int i = 0, j = 0, k = 0;
    while(i < M && j < N)
    {
        if(A[i] <= B[j])  C[k++] = A[i++];
        else  C[k++] = B[j++];
    }
    while(i < M)  C[k++] = A[i++];
    while(j < N)  C[k++] = B[j++];
}

返回主目錄

基數排序(Radix sorting)

【演算法】
Radix(int data[],int n) 
{   int t=1;
    while(n <= 10)
     {
        for(i = 0; i < 10; i++)
        {
            lsd = ((data[i] / n) % 10);
            temp[lsd][order[lsd]] = data[i];
            order[lsd]++;
        }
        if (t==1)  printf("\n「個位數」為主排序：");
        else   printf("\n「十位數」為主排序：");
        for(i = 0; i < 10; i++)
         {
            if(order[i] != 0)
                for(j = 0; j < order[i]; j++)
                {
                    data[k] = temp[i][j];
                    printf("%d ", data[k]);
                    k++;
                }
            order[i] = 0;
        }
        n *= 10;
        k = 0;
        t+=1;
    }
  }

返回主目錄

http://spaces.isu.edu.tw/upload/18833/3/web/sorting.htm



張貼者： 於 沒有留言:
標籤：
訂閱： 文章 (Atom)