七叶笔记 » golang编程 » 选择排序的三种语言实现

选择排序的三种语言实现

分类: golang编程 | 浏览: 581

思路：遍历数组，每一趟选择最小的数(指针j)，和前面(指针i)交换

C++实现: 

 template<typename T>
void selectionSort(T arr[], int n) {
  for (int i = 0; i < n; i++) { 
    int minIndex = i; 
    for (int j = i + 1; j < n; j++) { 
      if (arr[j] < arr[minIndex])
        minIndex = j;
    } 
    swap(arr[i], arr[minIndex]); 
  }
}

对对象进行排序：
struct  student  {
string name;
int score;
bool  operator <(const Student &otherStudent) {
//return score < otherStudent.score;
return score != otherStudent.score ? score < other Student .score : name < otherStudent.name;
}
friend  os tream& operator<<(ostream &os, const Student &student) {
os << "Student:" << student.name << " " << student.score << endl;
return os;
}
};

void main(){
    Student d[4] = { { "张三",90}, {"李四",100},{"王五",54} };
    selectionSort(d, 4);
    for (int i = 0; i < 4; i++) {
        cout << d[i];
    }
}

2.python实现: 

 #实现方式一：
def selectionSort(lst):
    for i in range(len(lst)):
        min_index = i
        for j in range(i + 1, len(lst)):
            if lst[j] < lst[min_index]:
                min_index = j
        lst[i], lst[min_index] = lst[min_index], lst[i]
 
#实现方式二：
def selectionSort2(lst):
    for i in range(len(lst)):
        min_index = lst.index(min(lst[i:]))
        lst[i], lst[min_index] = lst[min_index], lst[i]

#对对象进行排序:
class Student:
    def __init__(self,name,score):
        self.name=name
        self.score=score
    def __lt__(self, other):
        return self.score<other.score
    def __str__(self):
        return f'[{self.name},{self.score}]'

if __name__ == '__main__':
    students = [Student("小王",12),Student('小红',6),Student("小黑",2),Student('小灰',11)]
    selectionSort(students)
    for student in students:
        print(student)

3.golang实现： 

 func selectionSort(slice []int) {
    var minIndex, i, j int
    for i = 0; i < len(slice); i++ {
        minIndex = i
        for j = i + 1; j < len(slice); j++ {
            if slice[j] < slice[minIndex] {
                minIndex = j
            }
        }
        slice[i], slice[minIndex] = slice[minIndex], slice[i]
    }
}

// GoLang不支持运算符重载，所以不能直接对 结构体 进行排序，
//但可以使用sort.Sort 实现以下三个接口，对结构体数组/切片进行排序：
type Interface interface {
    // Len方法返回集合中的元素个数
    Len() int
    // Less方法报告索引i的元素是否比索引j的元素小
    Less(i, j int) bool
    // Swap方法交换索引i和j的两个元素
    Swap(i, j int)
}


type Student struct {
    Name  string
    Score float32
}
type StudentSlice []Student // 声明一个student的切片类型
func (s StudentSlice) Len() int {
    return len(s)
}
func (s StudentSlice) Less(i, j int) bool {
    return s[i].Score >= s[j].Score // 决定顺序 还是倒序
}
func (s StudentSlice) Swap(i, j int) {
    s[i], s[j] = s[j], s[i]
}

func main() {
    var students StudentSlice
    students = append(students, Student{"张三", 69.2})
    students = append(students, Student{"李四", 40.3})
    students = append(students, Student{"王五", 11.2})
    sort.Sort(students)
    fmt.Println(students)
}

选择排序为不稳定排序(如[6, 8, 6, 2]，第一遍循环，第一个6和2交换位置)，时间复杂度为 O(n^2)

相关文章