iT邦幫忙

1

系列篇章統整: 小馬的資料結構演算法筆記 (主要是用c++程式實作)

嗨嗨~ 大家好,
歡迎來到小馬的系列欄- 小馬的資料結構演算法筆記,
「資料結構」是資訊領域一個蠻重要的課題,
用意是如果我們能將資料整理的更有結構,
那麼使用上會更加方便,
比如說在一堆有排序過的物品中找東西,
一定比雜亂的垃圾堆中找東西容易。

返回主頁- 心原一馬用心經營自己的部落格,自開始寫文章以來所有篇章的總整理 #歡迎追蹤收藏

資料結構系列文

【小馬的資結演算法秘笈】(1)二分搜索法(Binary Search) #附c++程式教學
【小馬的資結演算法秘笈】(2)合併排序法- mergeSort
【小馬的資結演算法秘笈】(3)堆積排序法- heapSort
【小馬的資結演算法秘笈】(4) linked list 與 array比較
【小馬的資結演算法秘笈】(5) stack與queue
【小馬的資結演算法秘笈】(6)超好懂的圖(gragh)與樹(tree) 的觀念介紹
【小馬的資結演算法秘笈】(7) 在演算法中常見的BFS, DFS是什麼?
【小馬的資結演算法秘笈】(8) 有向圖(directed graph)及DAG(directed acyclic graph)的介紹
【小馬的資結演算法秘笈】(9) 做拓撲排序(topological sort)的兩種方法- 用queue及DFS
【小馬的資結演算法秘笈】(10) binary tree的四種走訪方式(preorder, inorder, postorder, level-order)
【小馬的資結演算法秘笈】(11) 四則運算與expression tree
【小馬的資結演算法秘笈】(12) 將infix表達式轉postfix(即普通四則運算式轉逆波蘭表達式)
【小馬的資結演算法秘笈】(13) Binary Search Tree,方便二分查找的樹
【小馬的資結演算法秘笈】(14) AVL tree簡介,會自動平衡的BST
【小馬的資結演算法秘笈】(15)Hash Table 簡介,平均O(1)時間查找的工具

問題集

資結經典題目: 用stack 解括號配對問題
資結經典題目: 用heap找前k個最小的數對
資結經典題目: 在二元樹中找最長路徑和
資結經典題目: 用stack計算逆波蘭表達式
資結經典題目: 計算字串四則運算的結果
資結經典題目: 實作一個Trie (又稱prefix tree、字典樹、前綴樹)
資結經典題目: 實作Dijkstra's algorithm,求graph中其中一個點到其它點的最短距離


1 則留言

0
ovo815428
iT邦新手 5 級 ‧ 2020-06-05 13:10:46

嗨~你好~我可以請教你關於PYTHON演算法插入排序與快速排序在實作上,程式區塊的意義為何,還有關鍵程式段與它的邏輯意義嗎?
我上網查過演算法的排序,用的程式語言不一樣,寫法也不一樣,雖然觀念可能差不多,但要看懂理解老師寫的,身邊一直找不到人可以問,想在這個平台上請教神人高手Orzzz拜託


def Insertion_Sort(data):
    size = 0
    i = 0
    
    print('\nPlease enter number to sort (enter 0 when end): ') # 要求輸入資料直到輸入為零
    while True:
        i += 1
        data.append(int(input('#%d number: ' % i)))
        if data[size] == 0:
            break
        size += 1

    for i in range(60):
        print('-', end = '')
    print()

    sorting(data, size)

    for i in range(60):
        print('-', end = '')

    print('\nSorted data : ', end = '')
    for i in range(size):
        print('%d ' % data[i], end = '')

def sorting(data, size):
    print('First data is %d\n' % data[0])

    ***# 當資料小於第一筆,則插於前方,否則與後面資料比對找出插入位置***
    for base in range(1, size):
        temp = data[base]
        compare = base
        print('Inserting data is ', data[base])
        while compare>0 and data[compare-1] > temp:
            data[compare] = data[compare-1]
            data[compare-1] = temp
            compare -= 1

        print('After #%d insertion: ' % base, end = '')
        for i in range(base+1):
            print(data[i], ' ', end = '')
        print('\n')

def main():
    data = []
    Insertion_Sort(data)

main()
# -*- coding: utf-8 -*-
"""
108-2 Data Structure

WK14-practice_14_2
"""

def quick_sort(data):
    size = 0
    i = 0

    print('\nPlease enter number to sort (enter 0 when end): ') # 要求輸入資料直到輸入為零
    while True:
        i += 1
        data.append(int(input('#%d number: ' % i)))
        if data[size] == 0:
            break
        size += 1

    for i in range(60):
        print('-', end = '')
    print()

    sorting(data, 0, size-1, size)

    for i in range(60):
        print('-', end = '')

    print('\nFinal sorted data: ', end = '')
    for i in range(size):
        print(data[i], ' ', end = '')

def sorting(data, left, right, size):
    #left與right分別代表欲排序資料兩端
    if left < right:
        lbase = left + 1
        while data[lbase] < data[left]:
            if lbase+1 > size:
                break
            lbase += 1
        rbase = right
        while data[rbase] > data[left]:
            rbase -= 1
        while lbase < rbase: # 若lbase小於rbase,則兩資料對調
            data[lbase], data[rbase] = data[rbase], data[lbase]
            lbase += 1
            while data[lbase] < data[left]:
                lbase += 1
            rbase -= 1
            while data[rbase] > data[left]:
                rbase -= 1
        data[left], data[rbase] = data[rbase], data[left] # 此時lbase大於rbase,則rbase的資料與第一筆對調
        
        print('Sorting: ', end = '')
        for i in range(size):
            print('%4d' % data[i], end = '')
        print()

        sorting(data, left, rbase-1, size)
        sorting(data, rbase+1, right, size)

def main():
    data = []
    quick_sort(data)

main()

嗨,您好,看了您的問題,
我覺得有必要了解你的學習背景,
以決定我該如何回覆您的問題,
因為我習慣因材施教、對症下藥的解決問題。

若經了解之後,我覺得其實問題不在演算法本身,
而在於一些更基礎的問題,
我也會直白告知。

我問你幾個問題(若你願意的話,用私訊的也可):

  1. 這門課是你買線上課程自學的,還是在學校內修課的?(高中或大學?)
  2. 在選這門課之前,你有學習過任何程式語言的基礎嗎?
  3. 若您是大學生的話,願意告訴我你的科系嗎?
  4. 你可以補充說明任何有助於我了解你的學習背景的描述。

我要留言

立即登入留言