【アルゴリズム】スタック、高速および集計ソート

python実装
一:ヒープソート
スタック配列は,スタックのデータ構造の性質を用いて並べ替えられ,その時間的複雑度はO(nlogn)であり,空間的複雑度は0(1)であり,1単位のみを用いて中間比較を行い,安定した並べ替えアルゴリズムではない.
主なアルゴリズム手順は次のとおりです.
ヒープH[0..n-1]を作成する
ヘッダー(最大値)とテールをに交換
並べ替えられる配列のサイズを1に縮小し、 を呼び出し、新しい配列の先端データを対応する位置に調整する.
ソート対象配列が0 になるまで手順2を繰り返します.

import os,MySort  
          
class HeapSort(MySort.MySort):  
     def __init__(self):    
        super(HeapSort, self).__init__("HeapSort", 8) #      init  ，               。  ，         
        self.data = self.init()
       
     def sort(self):  
          i = (len(self.data) - 1)/2 #   1  ，      ，       1。 1    
          print self.data
          while i >= 1:
              self.heapSort(i)
              i = i - 1
              
     def heapSort(self, index):  
          array = self.data  
          length = len(array) - 1
          d = array[index]
          l = 2 * index # get its child
          while (l < length):
              if (l + 1) <= length:
                  ld = array[l]
                  rd = array[l + 1]
                  if rd < ld:
                      l = l + 1
              if l <= length and d > array[l]:
                  array[index] = array[l]
                  index = l
              l = 2 * l
              
          array[index] = d 
                 
     def pop(self):  
         result = self.data[0]  
         self.reHeap(array)  
         
     def reHeap(self, data):  
           pass
       
     def outName(self):  
         super(HeapSort, self).outName()  
           
     def outData(self):  
          super(HeapSort, self).outData()  
            
if __name__ == "__main__":  
     s = HeapSort()  
     s.outName()  
     s.sort()  
     s.outData() 

ここでも1つのスタックについての小さいテーマを出して、スタックの高さが11であることを知っていて、スタックの最大のノードの個数と最小のノードの個数を求めますか?
スタックは一般的に二叉スタックと考えられていますが、それは完全な二叉木なので、第11層の最小要素は、最大でいっぱいで、これが最大と最小の個数です.
二:クイックソート
高速ソートはバブルソートの改良アルゴリズムであり、1回のソートによってデータをある数より大きい側とある数より小さい側に分け、ソートが完了するまで再帰的に操作する.これは平均性能の最良のソートであり,その最良の時間複雑度はO(nlgn),最悪の場合はO(n^2)である.不安定なソート方法でもあります.
アルゴリズムの手順:
1:数列から「基準」(支点)と呼ばれる要素を選択します.
2:配列の左端と右端をそれぞれ比較し、左端が基準より大きいものと右端が基準より小さいものを選び、左のポインタが右のポインタより大きいようにします.次に、基準値を配列に挿入します.このステップの終了は、基準値の左側が小さく、右側が大きくなります.
3:ステップ2を再帰的に実行します.

# -*- coding = utf8 -*-
from MySort import MySort


class QuickSort(MySort):
    def __init__(self):
        super(QuickSort, self).__init__("QuickSort", 8)  
        self.data = self.init()    
    
    def quickSort(self):
        if self.data == None:
            return
        print(self.data)
        self.sort(0, len(self.data) - 1)
        print(self.data)
        
    def sort(self, begin, end):
        if begin == end: return
        index = end
        pk = self.data[index]
        low = begin
        high = end
        while True:
            while self.data[low] <= pk and low < high:
                low += 1
            
            while self.data[high] >= pk and low < high:
                high -= 1
                
            self.data[low], self.data[high] = self.data[high], self.data[low]
            print(self.data)
            if low >= high: break
        #insert pk, here you can use high or low,because they are equal
        self.data[high], self.data[index] = pk, self.data[high]
        print(self.data)
        if begin < low:
            self.sort(begin, low - 1)
        self.sort(low, end)
if __name__ == "__main__":
    instance = QuickSort()
    instance.quickSort()
    

JAva実装
ソートアルゴリズムにとって、それは周波数を作るために使用されるアルゴリズムであり、多くのデータ構造と公式ライブラリにその具体的なインタフェースが実現されています.その応用が広範であるため、面接筆記試験でもよく提起される問題である.ここでは、いくつかの一般的なソートアルゴリズムについて説明します.スタック、クイックソート(クイックソート)、集計ソートが含まれます.
親、テストデータの初期化、統合インタフェースの作成:

import java.util.Random;

public abstract class Sort {
	
	/**
	 * init the input data
	 */
	public int[] init(){
		int[] input = new int[8];//should get from conf
		for(int i = 0; i < 8; i ++){
			input[i] = new Random().nextInt(20);
		}
		for(int i : input){
			System.out.print(i + " ");
		}
		System.out.println();
		return input;
	};

	/**
	 * main logic
	 */
	public abstract void sort();

	public abstract void printResult();
}

速排は、分治思想を利用して、泡のアップグレードです.ほとんどの場合、n*lognの複雑さを維持することができ、極端な場合、泡、n*nの複雑さに劣化する.

public class QuickSort extends Sort {
	private int[] input;

	@Override
	public int[] init() {
		input = super.init();
		return input;
	}

	@Override
	public void sort() {
		int end = input.length;
		sort(0, end - 1);
	}

	private void sort(int begin, int end) {
		if (begin == end)
			return;
		int index = end;
		int pk = input[end];
		int low = begin;
		int high = end;
		while (true) {
			while (input[low] <= pk && low < high)
				low++;
			while (input[high] >= pk && low < high)
				high--;
			int tmp = input[low];
			input[low] = input[high];
			input[high] = tmp;
			if (low == high)
				break;
		}
		int tmp = input[low];
		input[low] = pk;
		input[index] = tmp;
		if (begin < low) {
			sort(begin, low - 1);
		}
		sort(low, end);
	}

	@Override
	public void printResult() {
		for (int i : input) {
			System.out.print(i + " ");
		}
	}

	public static void main(String[] args) {
		QuickSort qs = new QuickSort();
		qs.init();
		qs.sort();
		qs.printResult();
	}
}