基础算法笔记 python和C++

二分查找

• python code

def binary_search(list,item):
    low=0
    high=len(list)-1

    while low<=high:
        mid=(low+high)//2
        guess=list[mid]
        if guess==item:
            return mid+1
        if guess<item:
            low=mid+1
        else:
            high=mid-1
    return None



my_list=[1,3,4,5,7,9,11]
print(binary_search(my_list,3))
print(binary_search(my_list,-1))

---

---

选择排序

• python code

def findSmallesr(arr):
    smallest=arr[0]       # save smallest value
    smallest_index=0      # save smallest index
    
    # 0~len-1
    for i in range(len(arr)):  
        if arr[i]<smallest:
            smallest=arr[i]
            smallest_index=i
    return smallest_index


def selectionSort(arr):
    new_array=[]
    for i in range(len(arr)):
        smallest_index=findSmallesr(arr)
        new_array.append(arr.pop(smallest_index))

    return new_array

print(selectionSort([5,6,46,2,15,38]))

• c++ code

#include <iostream> 
#include <string>   
using namespace std;


void printarray(int array[], int len)
{
    for (int i = 0; i < len; i++)
    {
        cout << array[i] << "->";
    }
}
void selectionsort(int array[], int len)//O(n*n)
{
    int i = 0;
    int j = 0;
    int k = 0;
    for (i = 0; i < len - 1; i++)
    {
        k = i;//记录最小元素
        for (j = i + 1; j < len; j++)
        {
            if (array[j] < array[k])
            {
                int temp = array[j];
                array[j] = array[k];
                array[k] = temp;
            }
        }
    }
}

int main()
{
    int array[] = { 3, 2, 1, 59, 69, 58, 45, 65, 87, 25, 98 };
    int len = sizeof (array) / sizeof(*array);
    printarray(array, len);
    selectionsort(array, len);
    printf("\n");
    printarray(array, len);
    system("pause");
    return 0;
}

---

---

快速排序

• python

def quicksort(arr):
    if len(arr)<2:
        return arr
    else:
        pivot=arr[0]
        less=[i for i in arr[1:] if i<pivot]
        greater=[i for i in arr[1:] if i>pivot]
    return quicksort(less)+[pivot]+quicksort(greater)


print(quicksort([32,5,6,76,87,4,5,21]))

• c++

#include <iostream> 
#include <string>   
using namespace std;

void printarray(int array[], int len)
{
    for (int i = 0; i < len; i++)
    {
        printf("%d->", array[i]);
    }
}

void swap(int array[], int i, int j)
{
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

int partion(int array[], int low, int high)
{
    int p = array[low];//枢轴取值
    while (low < high)
    {
        while ((p <= array[high]) && (low < high))
        {
            high--;
        }
        swap(array, low, high);
        while ((p >= array[low]) && (low < high))//与基准数比较
        {
            low++;
        }
        swap(array, low, high);
    }
    return low;//返回枢轴的位置 。。。很重要
}
void quicksort(int array[], int low, int high)
{
    if (low<high)
    {
        int povit = partion(array, low, high); //基准数的位置
        quicksort(array, low, povit - 1);
        quicksort(array, povit + 1, high);
    }
}


int main()
{
    int array[] = { 3, 2, 1, 59, 69, 58, 45, 65, 87, 25, 98, 5 };
    int len = sizeof (array) / sizeof(*array);
    printarray(array, len);
    quicksort(array, 0, len - 1);
    printf("\n");
    printarray(array, len);
    printf("\n");
    system("pause");
    return 0;
}