归并排序-Python and C++
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import random
#归并排序 mergeSort
# merge : 合并两个有序数组
def merge(left, right):
result = []
while left and right:
if left[0] <= right[0]:
result.append(left.pop(0))
else:
result.append(right.pop(0))
while left:
result.append(left.pop(0))
while right:
result.append(right.pop(0))
return result
def mergeSort(arr):
if len(arr) < 2:
return arr
middle = len(arr) / 2 #py2: 5/2=2(5/2.=2.5); py3: 5/2=2.5(5//2=2)
left, right = arr[:middle], arr[middle:]
return merge(mergeSort(left), mergeSort(right))
if __name__ == "__main__":
testList = [random.randint(0,99) for i in range(10)]
print 'test list:', testList
print 'after sort:', mergeSort(testList)
#include
#include
#include
#include
using namespace std;
///合并两个有序数组
vector merge(vector& left, vector& right)
{
vector result;
while((left.size() > 0) && (right.size() > 0)) {
if(left[0] <= right[0]) {
result.push_back(left[0]);
vector::iterator k = left.begin();
left.erase(k);
}
else {
result.push_back(right[0]);
vector::iterator k = right.begin();
right.erase(k);
}
}
while(left.size() > 0) {
result.push_back(left[0]);
vector::iterator k = left.begin();
left.erase(k);
}
while(right.size() > 0) {
result.push_back(right[0]);
vector::iterator k = right.begin();
right.erase(k);
}
return result;
}
vector mergeSort(vector& arr)
{
if(arr.size() < 2) return arr;
int middle = arr.size() / 2;
vector left(arr.begin(), arr.begin() + middle);
vector right(arr.begin() + middle, arr.end());
vector sortLeft = mergeSort(left);
vector sortRight = mergeSort(right);
return merge(sortLeft, sortRight);
}
int main()
{
vector testList;
std::default_random_engine e;
std::uniform_int_distribution u(0,99);
for(int i = 0; i < 10; i++) {
testList.push_back(u(e));
}
for(auto item : testList) {
cout << "item:" << item << endl;
}
vector afterSort = mergeSort(testList);
for(auto item : afterSort) {
cout << "after sort item:" << item << endl;
}
return 0;
}
作者：142857_T
